/**
Name demangler and mangled name based reflection facilities. Functions
defined in this module can be executed at compile time.

BUGS:

These compiler bugs must be fixed:
$(UL $(LI $(BUGZILLA 1972) - Foreach range statement breaks CTFE)
     $(LI $(BUGZILLA 2774) - Functions-as-properties makes it
          impossible to get the .mangleof a function)
     $(LI $(BUGZILLA 3026) - Segfault with incomplete static array
          initializer)
     $(LI $(BUGZILLA 3029) - Bug in array value mangling rule)
     $(LI $(BUGZILLA 3034) - Template instance name wrongly mangled as
          LName)
     $(LI $(BUGZILLA 3043) - Template symbol arg cannot be demangled)
     $(LI $(BUGZILLA 3050) - Allow exception in CTFE)
)
 */
module ext.demangle;

import std.stdint;

import ext.functional;
import ext.string;
import ext.traits;

public import ext.lang;

// Merge overload sets
private
{
    alias ext.string.toString toString;
}

private mixin (_throws_code);


//===================================================================//
// Internally-used stuffs
//===================================================================//

package bool isAsciiAlpha(char ch) pure nothrow
{
    return ('a' <= ch && ch <= 'z') ||
           ('A' <= ch && ch <= 'Z');
}


/*
string -> size_t convertion with overflow check
 */
static if (is(size_t == uintmax_t))
{
    private alias toUint toSize;
}
else
{
    private size_t toSize(string s) pure
    {
        const u = toUint(s);
        if (u > size_t.max)
            throw new Exception("size overflow");
        return cast(size_t) u;
    }
}

unittest
{
    static assert(toSize("0") == 0U);
    static assert(toSize("42") == 42U);

    static if (is(size_t == uint))
    {
        static assert(toSize("4294967295") == 4294967295U);
        static assert(throws!toSize("4294967296"));
    }
    static if (is(size_t == ulong))
    {
        static assert(toSize("18446744073709551615")
                == 18446744073709551615UL);
        static assert(throws!toSize("18446744073709551616"));
    }
}


/*
[workaround] (null).length blocks CTFE
 */
version (unittest)
private size_t length(T)(T[] arr) nothrow
{
    return arr ? arr.length : 0;
}


//===================================================================//
// Demangler
//===================================================================//

private struct Dummy(T...)
{
}

/* *************************************
[workaround]
 */
template mangleof(T)
{
    // S3ext8demangle__T5DummyT<...>Z5Dummy
    enum string mangleof = Dummy!(T).mangleof[23 .. $ - 7];
}

unittest
{
    static int foo() { return 0; }
    static assert(mangleof!(typeof(foo)) == "FZi");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// std.demangle compatibile interface
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
If the given string $(D name) is a valid D mangled symbol or type
_name, returns a natural string representation of the _name;
otherwise just returns $(D name).

Example:
--------------------
// mangled function name
string fun = demangle("_D3std4math3sinFNaNbeZe");
assert(fun == "pure nothrow real std.math.sin(real)");

// mangled template instance name
string temp = demangle("3std10functional__T9binaryFunVAyaa3_612b62Z");
assert(temp == `std.functional.binaryFun!("a+b")`);

// mangled type name
string type = demangle("HAyai");
assert(type == "string[int]");

// not a D mangled name
string name = demangle("errno");
assert(name == "errno");
--------------------
 */
string demangle(string name) /+pure+/ nothrow
{
    try
    {
        if (isQualifiedName(name))
            return toString(finish!parseQualifiedName(name));

        if (isMangledName(name))
            return toString(finish!parseMangledName(name));

        if (isType(name))
            return toString(finish!parseType(name));
    }
    catch
    {
    }
    return name;
}

unittest
{
    enum s1 = demangle("3std6traits__T6UnqualTxiZ");
    static assert(s1 == "std.traits.Unqual!(const(int))");

    enum s2 = demangle("_D3std4math3sinFNaNbeZe");
    static assert(s2 == "pure nothrow real std.math.sin(real)");

    enum s3 = demangle("Aya");
    static assert(s3 == "string");

    enum s4 = demangle("errno");
    static assert(s4 == "errno");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Demangle-based reflection
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the given string $(D n) as a mangled symbol name and returns a
$(D Symbol) object representing the symbol.

Throws:
$(D Exception) if $(D n) is not a valid mangled symbol name.

Example:
--------------------
// pure nothrow real std.math.sin(real x)
Symbol sym = decodeName("_D3std4math3sinFNaNbeZe");

assert(sym.name == "sin");
assert(sym.type.kind == Type.Kind.FUNCTION);
assert(sym.type.attributes ==
        FunctionAttribute.PURE | FunctionAttribute.NOTHROW);

Symbol parent = sym.parent[0];
assert(toString(sym) == "std.math");
--------------------
 */
Symbol decodeName(string n) pure
{
    if (isQualifiedName(n))
        return finish!parseQualifiedName(n);

    if (isMangledName(n))
        return finish!parseMangledName(n);

    error("not a D mangled name", n);
    assert(0);
}

unittest
{
    enum sym1 = decodeName("3std6traits__T6UniqueTxiZ");
    static assert(toString(sym1) == "std.traits.Unique!(const(int))");

    enum sym2 = decodeName(
            "_D3std7windows8iunknown8IUnknown6AddRefMFZk");
    static assert(toString(sym2) ==
            "uint std.windows.iunknown.IUnknown.AddRef()");
    static assert(sym2.type[0].needThis);

    static assert(throws!decodeName("4testZ")); // garbage
    static assert(throws!decodeName("Aya")); // not a name
}


/***************************************
Parses the given string $(D n) as a mangled type name and returns a
$(D Type) object representing the type.

Throws:
$(D Exception) if $(D n) is not a valid mangled type name.

Example:
--------------------
// immutable(char)[] a.k.a. string
Type type = decodeType("Aya");

// immutable(char)
Type etype = type.next[0];
assert(etype.kind == Type.Kind.CHAR)
assert(etype.storage == StorageClass.IMMUTABLE);
--------------------
 */
Type decodeType(string n) pure
{
    return finish!parseType(n);
}

unittest
{
    enum dn1 = decodeType("G42ya");
    static assert(toString(dn1) == "immutable(char)[42]");

    static assert(throws!decodeType("AyaZ")); // garbage
    static assert(throws!decodeType("3std")); // not a type
}


//===================================================================//
// Core
//===================================================================//

/*
$(D Demangle) contains a mangled name and the information $(D Content)
extracted from the mangled name.
 */
private struct Demangle(Content)
{
    // The mangled name corresponding to the $(D content).
    string mangle;

    // The extracted information.
    Content content;
}


/*
Parses $(D man) as a complete syntax.

This function calls $(D parse(man)) and returns the $(D content) field
of the result. An exception is thrown if there are garbages that has
not been parsed by $(D parse).
 */
private auto finish(alias parse)(string man) pure
{
    auto dem = parse(man);
    if (dem.mangle.length != man.length)
    {
        const rem = man[dem.mangle.length .. $];
        error("garbage at the end of the input", rem);
        assert(0);
    }
    return dem.content;
}


/*
Throws an exception with the error message $(D msg).

Params:
  msg = The error message.
  man = The mangled name closely related to the error.
 */
private void error(string msg, string man) pure
{
    throw new Exception(msg);
}


/*
Invokes $(D error(msg, man)) if $(D pred == false), or do nothing
otherwise.
 */
private void expect(bool pred, string msg, string man) pure
{
    if (!pred)
        error(msg, man);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// General
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a Number and returns it.

--------------------
Number:
    Digit
    Digit Number
--------------------
 */
private Demangle!(string) parseNumber(string man) pure
{
    auto num = span!(isDigit)(man);
    expect(num.length != 0, "decimal digit expected", man);

    return typeof(return)(man[0 .. num.length], num);
}

unittest
{
    enum dem1 = parseNumber("123x");
    static assert(dem1.mangle == "123");
    static assert(dem1.content == "123");

    enum dem2 = parseNumber("9999999999999999999999999");
    static assert(dem2.mangle == "9999999999999999999999999");
    static assert(dem2.content == "9999999999999999999999999");

    static assert(throws!parseNumber("-42")); // sign
    static assert(throws!parseNumber("")); // empty
}

// Returns true if the letter ch matches Digit.
package bool isDigit(char ch) pure nothrow
{
    return '0' <= ch && ch <= '9';
}

// Returns true if the string man is expected to be a Number.
private bool isNumber(string man) pure nothrow
{
    return man.length && isDigit(man[0]);
}


/***************************************
Parses the string $(D man) as a HexNumber and returns it.

--------------------
HexNumber:
    HexDigit
    HexDigit HexNumber
--------------------
 */
private Demangle!(string) parseHexNumber(string man) pure
{
    auto num = span!(isHexDigit)(man);
    expect(num.length != 0, "hexadecimal digit expected", man);

    return typeof(return)(man[0 .. num.length], num);
}

unittest
{
    enum dem1 = parseHexNumber("1AFx");
    static assert(dem1.mangle == "1AF");
    static assert(dem1.content == "1AF");

    enum dem2 = parseHexNumber("FFFFFFFFFFFFFFFFFFFFFFFFF");
    static assert(dem2.mangle == "FFFFFFFFFFFFFFFFFFFFFFFFF");
    static assert(dem2.content == "FFFFFFFFFFFFFFFFFFFFFFFFF");

    static assert(throws!parseHexNumber("abc")); // lowercase
    static assert(throws!parseHexNumber("")); // empty
}

// Returns true if the letter ch matches HexFloat.
package bool isHexDigit(char ch) pure nothrow
{
    return isDigit(ch) || ('A' <= ch && ch <= 'F');
}

// Returns true if the string man is expected to be a HexNumber.
private bool isHexNumber(string man) pure nothrow
{
    return man.length && isHexDigit(man[0]);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Type
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a mangled type name and returns a
$(D Type) object representing the type.
 */
private Demangle!(Type) parseType(string man) pure
out
{
    assert(isType(man));
}
body
{
    switch (man.length ? man[0] : char.init)
    {
        case 'O', // Shared
             'x', // Const
             'y': // Invariant
            return parseTypeStoc(man);

        case 'A': // TypeArray
            return parseTypeArray(man);

        case 'G': // TypeSArray
            return parseTypeStaticArray(man);

        case 'H': // TypeAarray
            return parseTypeAssocArray(man);

        case 'P': // TypePointer
            return parseTypePointer(man);

        case 'F', 'U', 'W', 'V', 'R': // TypeFunction
            return parseTypeFunction(man);

        case 'I', // TypeIdent
             'C', // TypeClass
             'S', // TypeStruct
             'E', // TypeEnum
             'T': // TypeTypedef
            return parseTypeIdent(man);

        case 'D': // TypeDelegate
            return parseTypeDelegate(man);

        case 'n', // TypeNone
             'v', // TypeVoid
             'g', // TypeByte
             'h', // TypeUbyte
             's', // TypeShort
             't', // TypeUshort
             'i', // TypeInt
             'k', // TypeUint
             'l', // TypeLong
             'm', // TypeUlong
             'f', // TypeFloat
             'd', // TypeDouble
             'e', // TypeReal
             'o', // TypeIfloat
             'p', // TypeIdouble
             'j', // TypeIreal
             'q', // TypeCfloat
             'r', // TypeCdouble
             'c', // TypeCreal
             'b', // TypeBool
             'a', // TypeChar
             'u', // TypeWchar
             'w': // TypeDchar
            return parseTypeBasic(man);

        case 'B': // TypeTuple
            return parseTypeTuple(man);

        default:
            error("not a type", man);
            assert(0);
    }
}

unittest
{
    static assert(throws!parseType("0")); // not a type
    static assert(throws!parseType("")); // empty
}

// Returns true if the string man is expected to be a Type.
private bool isType(string man) pure nothrow
{
    static immutable bool[char.max + 1] TYPE_CHARS =
    [
        'O': true, 'x': true, 'y': true,
        'A': true, 'G': true, 'H': true, 'P': true,
        'F': true, 'U': true, 'W': true, 'V': true, 'R': true,
        'I': true, 'C': true, 'S': true, 'E': true, 'T': true,
        'D': true,
        'n': true, 'v': true,
        'g': true, 's': true, 'i': true, 'l': true,
        'h': true, 't': true, 'k': true, 'm': true,
        'f': true, 'd': true, 'e': true,
        'o': true, 'p': true, 'j': true,
        'q': true, 'r': true, 'c': true,
        'b': true, 'a': true, 'u': true, 'w': true,
        'B': true
    ];
    return man.length && TYPE_CHARS[man[0]];
}


/***************************************
Parses the string $(D man) as a mangled storage class and a type name
and returns a $(D Type) object representing the type and the storage
class.

--------------------
StorageClass:
    Shared
    Const
    Invariant

Shared:
    O Type

Const:
    x Type

Invariant:
    y Type
--------------------
 */
private Demangle!(Type) parseTypeStoc(string man) pure
{
    string rem = man;

    // the storage class
    alias StorageClass STC;
    STC stoc;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'O': stoc = STC.   SHARED; break;
        case 'x': stoc = STC.    CONST; break;
        case 'y': stoc = STC.IMMUTABLE; break;

        default:
            error("not a storage class", man);
            assert(0);
    }
    rem = rem[1 .. $];

    // Extract the modified type. Note: Another storage class may be
    // applied to the modified type (in the case of shared const), so
    // we must add (or-assign) the storage class, not assign it.
    Type modty;

    auto next = parseType(rem);
    rem   = rem[next.mangle.length .. $];
    modty = next.content;

    // Add the storage class.
    modty.storage |= stoc;

    return typeof(return)(man[0 .. $ - rem.length], modty);
}

unittest
{
    enum dem1 = parseType("OiZ");
    static assert(dem1.mangle == "Oi");
    static assert(toString(dem1.content) == "shared(int)");

    enum dem2 = parseType("xiZ");
    static assert(dem2.mangle == "xi");
    static assert(toString(dem2.content) == "const(int)");

    enum dem3 = parseType("yiZ");
    static assert(dem3.mangle == "yi");
    static assert(toString(dem3.content) == "immutable(int)");

    enum dem4 = parseType("OxiZ");
    static assert(dem4.mangle == "Oxi");
    static assert(toString(dem4.content) == "shared(const(int))");

    static assert(throws!parseTypeStoc("i")); // no storage class
    static assert(throws!parseTypeStoc("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled dynamic array type name and
returns a $(D Type) object representing the type.

--------------------
TypeArray:
    A Type
--------------------
 */
private Demangle!(Type) parseTypeArray(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "A"), "not an array type", rem);
    rem = rem[1 .. $];

    // the element type
    auto etype = parseType(rem);
    rem = rem[etype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.ARRAY;
    ty.next = [ etype.content ];

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("AiZ");
    static assert(dem1.mangle == "Ai");
    static assert(toString(dem1.content) == "int[]");

    static assert(throws!parseTypeArray("AZ")); // no type
    static assert(throws!parseTypeArray("i")); // not an array
    static assert(throws!parseTypeArray("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled static array type name and
returns a $(D Type) object representing the type.

--------------------
TypeSarray:
    G Number Type
--------------------
 */
private Demangle!(Type) parseTypeStaticArray(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "G"), "not a static array type", rem);
    rem = rem[1 .. $];

    // the dimension of the static array
    auto dim = parseNumber(rem);
    rem = rem[dim.mangle.length .. $];

    // the element type
    auto etype = parseType(rem);
    rem = rem[etype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind   = Type.Kind.SARRAY;
    ty.next   = [ etype.content ];
    ty.length = toSize(dim.content);

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("G42iZ");
    static assert(dem1.mangle == "G42i");
    static assert(toString(dem1.content) == "int[42]");

    enum dem2 = parseType("G0i");
    static assert(dem2.mangle == "G0i");
    static assert(toString(dem2.content) == "int[0]");

    enum dem3 = parseType("G4294967295i");
    static assert(dem3.mangle == "G4294967295i");
    static assert(toString(dem3.content) == "int[4294967295]");

    static assert(throws!parseTypeStaticArray("G42")); // no type
    static assert(throws!parseTypeStaticArray("Gi")); // no dim
    static assert(throws!parseTypeStaticArray("G")); // neither
    static assert(throws!parseTypeStaticArray("i")); // invalid
    static assert(throws!parseTypeStaticArray("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled associative array type name and
returns a $(D Type) object representing the type.

--------------------
TypeAarray:
    H Type Type
--------------------
 */
private Demangle!(Type) parseTypeAssocArray(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "H"), "not an associative array type", rem);
    rem = rem[1 .. $];

    // Extract the referenced types. The value type precedes.
    auto vtype = parseType(rem);
    rem = rem[vtype.mangle.length .. $];

    auto ktype = parseType(rem);
    rem = rem[ktype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.AARRAY;
    ty.next = [ ktype.content, vtype.content ]; // key precedes

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("HieZ");
    static assert(dem1.mangle == "Hie");
    static assert(toString(dem1.content) == "int[real]");

    static assert(throws!parseTypeAssocArray("HiZ")); // no key
    static assert(throws!parseTypeAssocArray("HZ")); // no v/k
    static assert(throws!parseTypeAssocArray("i")); // invalid
    static assert(throws!parseTypeAssocArray("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled pointer type name and returns a
$(D Type) object representing the type.

--------------------
TypePointer:
    P Type
--------------------
 */
private Demangle!(Type) parseTypePointer(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "P"), "not a pointer type", rem);
    rem = rem[1 .. $];

    // the referenced type
    auto etype = parseType(rem);
    rem = rem[etype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.POINTER;
    ty.next = [ etype.content ];

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("PiZ");
    static assert(dem1.mangle == "Pi");
    static assert(toString(dem1.content) == "int*");

    static assert(throws!parseTypePointer("PZ")); // no type
    static assert(throws!parseTypePointer("i")); // not a pointer
    static assert(throws!parseTypePointer("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled function type name and returns
a $(D Type) object representing the type.

--------------------
TypeFunction:
    CallConvention FuncAttrs Arguments ArgClose Type

CallConvention:
    F       // D
    U       // C
    W       // Windows
    V       // Pascal
    R       // C++

FuncAttrs:
    empty
    FuncAttr
    FuncAttr FuncAttrs

FuncAttr:
    Na      // pure
    Nb      // nothrow
    Nc      // ref

ArgClose
    X       // variadic T t...) style
    Y       // variadic T t,...) style
    Z       // not variadic
--------------------
 */
private Demangle!(Type) parseTypeFunction(string man) pure
{
    string rem = man;

    /* A mangled function type name starts with a letter that indicates
     * the calling convention. The letter must not be omitted.
     */
    Linkage conv;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'F': conv = Linkage.      D; break;
        case 'U': conv = Linkage.      C; break;
        case 'W': conv = Linkage.WINDOWS; break;
        case 'V': conv = Linkage. PASCAL; break;
        case 'R': conv = Linkage.    CPP; break;

        default:
            error("not a function type", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    /* Extract zero or more function attributes. A function attribute
     * is mangled to an ASCII letter preceded by another letter 'N'.
     */
    FunctionAttribute atts;

    while (rem.length >= 2 && rem[0] == 'N')
    {
        alias FunctionAttribute Attr;

        switch (rem[1])
        {
            case 'a': atts |= Attr.   PURE; break;
            case 'b': atts |= Attr.NOTHROW; break;
            case 'c': atts |= Attr.    REF; break;

            default:
                error("invalid function attribute", rem);
                assert(0);
        }
        rem = rem[2 .. $];
    }

    /* Extract the parameter type list. The number of parameters is not
     * given. Just extract types until encountering an ArgClose.
     */
    auto args = parseArguments(rem);
    rem = rem[args.mangle.length .. $];

    /* There must be a letter indicating the function variadicity:
     *   'X' => typesafe
     *   'Y' => argptr
     *   'Z' => not variadic
     */
    Variadic var;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'X': var = Variadic.TYPESAFE; break;
        case 'Y': var = Variadic.VARIADIC; break;
        case 'Z':   /* not variadic */     break;

        default:
            error("X, Y or Z expected", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    // the return type
    auto rtype = parseType(rem);
    rem = rem[rtype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind       = Type.Kind.FUNCTION;
    ty.next       = rtype.content ~ args.content;
    ty.linkage    = conv;
    ty.attributes = atts;
    ty.variadic   = var;

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("FisZd0");
    static assert(dem1.mangle == "FisZd");
    static assert(toString(dem1.content) == "double(int, short)");

    enum dem2 = parseType("UNbNckMAxiXe0");
    static assert(dem2.mangle == "UNbNckMAxiXe");
    static assert(toString(dem2.content) ==
            "extern(C) nothrow ref real(uint, scope const(int)[]...)");

    enum dem3 = parseType("FYv0");
    static assert(dem3.mangle == "FYv");
    static assert(toString(dem3.content) == "void(...)");

    alias throws!parseTypeFunction invalid;
    static assert(invalid("F0")); // no return type
    static assert(invalid("FZ0")); // no return type
    static assert(invalid("FNzZv0")); // invalid attr
    static assert(invalid("Z")); // not a function
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as up to $(D max) mangled function parameter
type names and returns an array of $(D Type) objects representing the
parameter types.

--------------------
Arguments:
    Argument
    Argument Arguments

Argument:
    Argument2
    M Argument2     // scope

Argument2:
    Type
    J Type      // out
    K Type      // ref
    L Type      // lazy
--------------------
 */
private Demangle!(Type[]) parseArguments(
        in string man, size_t max = size_t.max) pure
{
    string rem = man;
    Type[] args;

    foreach (i; 0 .. max)
    {
        alias StorageClass STC;

        if (!rem.length || isArgClose(rem))
            break;

        /* Extract a parameter storage class. Beware of the possible
         * lazy scope storage class.
         */
        STC stc;

        while (rem.length)
        {
            STC c;

            switch (rem[0])
            {
                case 'M': c = STC.SCOPE; break;
                case 'J': c = STC.  OUT; break;
                case 'K': c = STC.  REF; break;
                case 'L': c = STC. LAZY; break;
                default: break;
            }
            if (c == STC.init)
                break; // no storage class

            // accumulate
            stc |= c;
            rem  = rem[1 .. $];
        }

        /* Extract a parameter type and add the parameter storage
         * class. Note: The parameter storage is independent of a
         * possible type-constructing storage class, so we must add
         * (or-assign) the parameter storage class, not assign it.
         */
        Type arg;

        auto type = parseType(rem);
        rem = rem[type.mangle.length .. $];
        arg = type.content;

        // Add the parameter storage class.
        arg.storage |= stc;

        // accumulate
        args ~= arg;
    }

    // Done.
    return typeof(return)(man[0 .. $ - rem.length], args);
}

unittest
{
    enum dem1 = parseArguments("iZ");
    static assert(dem1.mangle == "i");
    static assert(dem1.content.length == 1);
    static assert(toString(dem1.content[0]) == "int");

    enum dem2 = parseArguments("ike");
    static assert(dem2.mangle == "ike");
    static assert(dem2.content.length == 3);
    static assert(toString(dem2.content[0]) ==  "int");
    static assert(toString(dem2.content[1]) == "uint");
    static assert(toString(dem2.content[2]) == "real");

    enum dem3 = parseArguments("MLAxiZ");
    static assert(dem3.mangle == "MLAxi");
    static assert(dem3.content.length == 1);
    static assert(toString(dem3.content[0]) ==
            "lazy scope const(int)[]");

    enum dem4 = parseArguments("ike", 1);
    static assert(dem4.mangle == "i");
    static assert(dem4.content.length == 1);
    static assert(toString(dem4.content[0]) ==  "int");

    enum dem5 = parseArguments("");
    static assert(dem5.content == null);
}

// Returns true if the string man matches ArgClose.
private bool isArgClose(string man) pure nothrow
{
    switch (man.length ? man[0] : char.init)
    {
        case 'X', 'Y', 'Z': return  true;
        default           : return false;
    }
}


/***************************************
Parses the string $(D man) as a mangled user-defined type name and
returns a $(D Type) obejct representing the type.

A mangled user-defined type name only contains the user-defined name.

--------------------
TypeUser:
    TypeIdent
    TypeClass
    TypeStruct
    TypeEnum
    TypeTypedef

TypeIdent:
    I QualifiedName

TypeClass:
    C QualifiedName

TypeStruct:
    S QualifiedName

TypeEnum:
    E QualifiedName

TypeTypedef:
    T QualifiedName
--------------------
 */
private Demangle!(Type) parseTypeIdent(string man) pure
{
    alias Type.Kind T;
    string rem = man;

    // which type?
    T kind;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'I': kind = T.  IDENT; break;
        case 'C': kind = T.  CLASS; break;
        case 'S': kind = T. STRUCT; break;
        case 'E': kind = T.   ENUM; break;
        case 'T': kind = T.TYPEDEF; break;

        default:
            error("I, C, S, E or T expected", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    // the user-defined name
    auto name = parseQualifiedName(rem);
    rem = rem[name.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind   = kind;
    ty.symbol = [ name.content ];

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    alias Type.Kind T;

    enum dem1 = parseType("S3std5regex6EngineV");
    enum t1   = dem1.content;
    static assert(dem1.mangle == "S3std5regex6Engine");
    static assert(t1.kind == T.STRUCT);
    static assert(toString(t1.symbol[0]) == "std.regex.Engine");

    enum dem2 = parseType("C3Foo");
    enum t2   = dem2.content;
    static assert(dem2.mangle == "C3Foo");
    static assert(t2.kind == T.CLASS);
    static assert(toString(t2.symbol[0]) == "Foo");

    static assert(throws!parseTypeIdent("IZ")); // no qname
    static assert(throws!parseTypeIdent("")); //empty
}


/***************************************
Parses the string $(D man) as a mangled delegate type name and returns
a $(D Type) object representing the type.

--------------------
TypeDelegate:
    D TypeFunction
--------------------
 */
private Demangle!(Type) parseTypeDelegate(string man) pure
{
    string rem = man;

    // TypeDelegate is actually a TypeFunction prefixed by "D"
    expect(startsWith(rem, "D"), "not a delegate type", rem);
    rem = rem[1 .. $];

    auto fun = parseTypeFunction(rem);
    rem = rem[fun.mangle.length .. $];

    // Mark the returned function type as a delegate.
    Type ty = fun.content;
    ty.kind = Type.Kind.DELEGATE;

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("DFNcAiXiZ");
    static assert(dem1.mangle == "DFNcAiXi");
    static assert(toString(dem1.content) == "ref int delegate(int[]...)");

    static assert(throws!parseTypeDelegate("FZv")); // not a dg
    static assert(throws!parseTypeDelegate("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled basic type name and returns a
$(D Type) object representing the type.
 */
private Demangle!(Type) parseTypeBasic(string man) pure
{
    alias Type.Kind T;

    expect(man.length != 0, "out of input", man);

    /* Use static array to map a mangled basic type name c to the
     * corresponding type kind. Invalid mangled name will be mapped to
     * T.init, which equals to T.NONE. However, T.NONE is a valid type
     * kind whose mangled name is 'n', so a special treatment will be
     * needed for c == 'n' when we are checking the input for an error.
     */
    static immutable T[0x80] MAP =
    [
        'n': T.  NONE, 'v': T.   VOID,
        'g': T.  BYTE, 's': T.  SHORT, 'i': T.  INT, 'l': T. LONG,
        'h': T. UBYTE, 't': T. USHORT, 'k': T. UINT, 'm': T.ULONG,
        'f': T. FLOAT, 'd': T. DOUBLE, 'e': T. REAL,
        'o': T.IFLOAT, 'p': T.IDOUBLE, 'j': T.IREAL,
        'q': T.CFLOAT, 'r': T.CDOUBLE, 'c': T.CREAL,
        'b': T.  BOOL, 'a': T.   CHAR, 'u': T.WCHAR, 'w': T.DCHAR,
    ];
    const c = man[0];

    if (c >= MAP.length || (c != 'n' && MAP[c] == T.init))
        error("not a basic type", man);

    return typeof(return)(man[0 .. 1], Type(MAP[c]));
}

unittest
{
    enum dem1 = parseType("ik");
    static assert(dem1.mangle == "i");
    static assert(toString(dem1.content) == "int");

    static assert(throws!parseTypeBasic("xi")); // storage class
    static assert(throws!parseTypeBasic("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled type tuple and returns a
$(D Type) object representing the type.

--------------------
TypeTuple:
    B Number Arguments
--------------------
 */
private Demangle!(Type) parseTypeTuple(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "B"), "not a type tuple", rem);
    rem = rem[1 .. $];

    // the number of items in the type tuple
    auto nargs = parseNumber(rem);
    rem = rem[nargs.mangle.length .. $];

    const dim = toSize(nargs.content);

    // Extract the items in the type tuple. Note: parseArguments
    // stops at (possible) ArgClose even if the number of extracted
    // items is less than dim.
    auto args = parseArguments(rem, dim);
    rem = rem[args.mangle.length .. $];

    expect(args.content.length == dim, "type tuple out of items", rem);

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.TUPLE;
    ty.next = args.content;

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("B0Z");
    static assert(dem1.mangle == "B0");
    static assert(toString(dem1.content) == "()");

    enum dem2 = parseType("B2ixk");
    static assert(dem2.mangle == "B2ixk");
    static assert(toString(dem2.content) == "(int, const(uint))");

    static assert(throws!parseTypeTuple(
                "B9999999999999999999999999z")); // overflow
    static assert(throws!parseTypeTuple("B2iZ")); // out of item
    static assert(throws!parseTypeTuple("Bz")); // no number
    static assert(throws!parseTypeTuple("B100")); // no type
}


/***************************************
Parses the string $(D man) as a SymbolType. SymbolType is used in
Symbol and MangledName for representing the type of a symbol.

--------------------
SymbolType:
    Type
    M Type
--------------------
 */
private Demangle!(Type) parseSymbolType(string man) pure
{
    string rem = man;

    // A possible preceding M indicates that the symbol is a function
    // that needs a context pointer.
    bool needthis;

    if (startsWith(rem, "M"))
    {
        needthis = true;
        rem = rem[1 .. $];
    }

    // the symbol type
    auto demty = parseType(rem);
    rem = rem[demty.mangle.length .. $];

    auto type = demty.content;
    type.needThis = needthis;

    return typeof(return)(man[0 .. $ - rem.length], type);
}

unittest
{
    enum st1 = parseSymbolType("MFZv");
    static assert(st1.content.needThis);
}

// Returns true if the string man is expected to be a SymbolType.
private bool isSymbolType(string man) pure nothrow
{
    return startsWith(man, "M") || isType(man);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Symbol name
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Returns $(D true) if the string $(D id) is a valid identifier.

--------------------
Identifier:
    IdentiferStart
    IdentiferStart IdentifierChars

IdentifierChars:
    IdentiferChar
    IdentiferChar IdentifierChars

IdentifierStart:
    _
    Letter
    UniversalAlpha

IdentifierChar:
    IdentiferStart
    0
    NonZeroDigit
--------------------
 */
private bool isIdentifier(string id) pure nothrow
{
    static bool isIdentifierStart(char ch) pure nothrow
    {
        return ('a' <= ch && ch <= 'z') ||
               ('A' <= ch && ch <= 'Z') ||
               (ch == '_') || (ch >= 0x80);
    }

    static bool isIdentifierChar(char ch) pure nothrow
    {
        return isIdentifierStart(ch) ||
               ('0' <= ch && ch <= '9');
    }

    if (!id.length || !isIdentifierStart(id[0]))
        return false;

    foreach (c; id[1 .. $])
    {
        if (!isIdentifierChar(c))
            return false;
    }
    return true;
}

unittest
{
    static assert( isIdentifier("__unittest1"));
    static assert( isIdentifier("errno"));
    static assert( isIdentifier("\u03B1"));
    static assert(!isIdentifier("4test"));
    static assert(!isIdentifier(" "));
}


/***************************************
Parses the string $(D man) as a mangled qualified name and returns a
$(D Symbol) object representing the qualified name.

--------------------
QualifiedName:
    TypedSymbol
    TypedSymbol QualifiedName

TypedSymbol:
    Symbol
    Symbol SymbolType
--------------------
 */
private Demangle!(Symbol) parseQualifiedName(string man) pure
{
    string rem = man;

    Symbol qname;
    uint   depth;
    do
    {
        Symbol segment;

        auto sym = parseSymbolName(rem);
        rem     = rem[sym.mangle.length .. $];
        segment = sym.content;

        // Functions and variables have their own types. Beware of
        // nested functions; in such case intermediate segments may
        // have types (not documented in the ABI).
        if (isSymbolType(rem))
        {
            try
            {
                auto type = parseSymbolType(rem);
                rem          = rem[type.mangle.length .. $];
                segment.type = [ type.content ];
            }
            catch
            {
                // May have wrongly parsed a template value parameter
                // "V..." as a function type. It can happen.
            }
        }

        // Connect to the parent segment.
        if (++depth > 1)
            segment.parent = [ qname ];
        qname = segment;
    }
    while (isSymbolName(rem))

    return typeof(return)(man[0 .. $ - rem.length], qname);
}

unittest
{
    enum dem1 = parseQualifiedName("3std4math");
    static assert(dem1.mangle == "3std4math");
    static assert(toString(dem1.content) == "std.math");

    enum dem2 = parseQualifiedName("3std6traits__T6UnqualTxiZZ");
    static assert(dem2.mangle == "3std6traits__T6UnqualTxiZ");
    static assert(toString(dem2.content) ==
            "std.traits.Unqual!(const(int))");

    static assert(throws!parseQualifiedName("zzz")); // invalid
    static assert(throws!parseQualifiedName("")); // empty
}

// Returns true if the string man is expected to be a QualifiedName.
private bool isQualifiedName(string man) pure nothrow
{
    return isSymbolName(man);
}


/***************************************
Parses the string $(D man) as a mangled symbol name and returns a
$(D Symbol) object representing the symbol.

--------------------
Symbol:
    LName
    TemplateInstanceName
    main                    // special name
--------------------
 */
private Demangle!(Symbol) parseSymbolName(string man) pure
{
    if (isLName(man))
    {
        string rem = man;
        Symbol sym;

        auto lname = parseLName(rem);
        rem = rem[lname.mangle.length .. $];
        sym = lname.content;

        // [workaround] Bugzilla #3034
        if (isTemplateInstanceName(sym.name))
        {
            try
            {
                sym = finish!parseTemplateInstanceName(sym.name);
            }
            catch {}
        }

        return typeof(return)(man[0 .. $ - rem.length], sym);
    }
    else if (isTemplateInstanceName(man))
    {
        return parseTemplateInstanceName(man);
    }
    else if (isSpecialSymbol(man))
    {
        return parseSpecialSymbol(man);
    }

    error("not a symbol", man);
    assert(0);
}

unittest
{
    enum dem1 = parseSymbolName("3ext0");
    static assert(dem1.mangle == "3ext");
    static assert(toString(dem1.content) == "ext");

    enum dem2 = parseSymbolName("__T4TestZ0");
    static assert(dem2.mangle == "__T4TestZ");
    static assert(toString(dem2.content) == "Test!()");

    static assert(throws!parseSymbolName("0")); // not an ident
    static assert(throws!parseSymbolName("_D4testi")); // not a sym
    static assert(throws!parseSymbolName("")); // empty
}

// Returns true if the string man is expected to be a Symbol.
private bool isSymbolName(string man) pure nothrow
{
    return isLName(man) ||
           isTemplateInstanceName(man) ||
           isSpecialSymbol(man);
}


/***************************************
Parses the string $(D man) as a mangled identifier name and returns a
$(D Symbol) object representing the identifier.

--------------------
LName:
    Number Name
--------------------
 */
private Demangle!(Symbol) parseLName(string man) pure
{
    string rem = man;

    // Extract the length of the identifier. Note that the length may
    // be too big v.s. the input string.
    auto num = parseNumber(rem);
    rem = rem[num.mangle.length .. $];

    expect(rem.length >= toSize(num.content), "out of input", rem);

    // Extract the identifier by simply slicing the input. Note that
    // the obtained string may not be a valid identifier.
    const id = rem[0 .. toSize(num.content)];
    expect(isIdentifier(id), "invalid identifier: " ~ id, rem);
    rem = rem[id.length .. $];

    // Compose a Symbol object.
    Symbol sym;
    sym.kind = Symbol.Kind.IDENTIFIER;
    sym.name = id;

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseLName("3std0");
    static assert(dem1.mangle == "3std");
    static assert(toString(dem1.content) == "std");

    alias throws!parseLName invalid;
    static assert(invalid("42a")); // out of input
    static assert(invalid("8std.math")); // invalid identifier
    static assert(invalid("__T4TestZ")); // not an LName
    static assert(invalid("")); // empty

    // overflow
    enum max = toString(cast(uintmax_t) size_t.max);
    static assert(invalid(max ~ "z"));
}

// Returns true if the string man is expected to be an LName.
private bool isLName(string man) pure nothrow
{
    return isNumber(man);
}


/***************************************
Parses the string $(D man) as a mangled template instance name and
returns a $(D Symbol) object representing the template instance.

--------------------
TemplateInstanceName:
     __T LName TemplateArgs Z

TemplateArgs:
    TemplateArg
    TemplateArg TemplateArgs
--------------------
 */
private Demangle!(Symbol) parseTemplateInstanceName(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "__T"), "not a template instance name", rem);
    rem = rem[3 .. $];

    // the name of the instantiated template itself
    auto name = parseLName(rem);
    rem = rem[name.mangle.length .. $];

    // the template instantiation arguments
    TemplateArgument[] args;

    while (isTemplateArg(rem))
    {
        auto ta = parseTemplateArg(rem);
        rem   = rem[ta.mangle.length .. $];
        args ~= ta.content;
    }

    // expect "Z"
    expect(startsWith(rem, "Z"), "template instance not closed", rem);
    rem = rem[1 .. $];

    // Compose a Symbol object for the template instance.
    Symbol sym;
    sym.kind = Symbol.Kind.TEMPLATE;
    sym.name = name.content.name;
    sym.args = args;

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseTemplateInstanceName("__T4TestZ0");
    static assert(dem1.mangle == "__T4TestZ");
    static assert(toString(dem1.content) == "Test!()");

    enum dem2 = parseTemplateInstanceName("__T4TestTiVii42Z");
    static assert(dem2.mangle == "__T4TestTiVii42Z");
    static assert(toString(dem2.content) == "Test!(int, 42)");

    alias throws!parseTemplateInstanceName invalid;
    static assert(invalid("__T4Test")); // no Z
    static assert(invalid("__TTiZ")); // no LName
    static assert(invalid("4Test")); // not TIN
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a
// TemplateInstanceName.
private bool isTemplateInstanceName(string man) pure nothrow
{
    return startsWith(man, "__T");
}


/***************************************
Parses the string $(D man) as a mangled template argument and returns
a $(D TemplateArgument) object representing the template argument.

--------------------
TemplateArg:
    T Type
    V Type Value
    S TemplateSymbolArg

TemplateSymbolArg:
    M LName
    QualifiedName
--------------------
 */
private Demangle!(TemplateArgument) parseTemplateArg(string man) pure
{
    // hub
    switch (man.length ? man[0] : char.init)
    {
        case 'T': return parseTemplateTypeArg(man);
        case 'V': return parseTemplateValueArg(man);
        case 'S': return parseTemplateSymbolArg(man);

        default:
            error("not a template argument", man);
            assert(0);
    }
}

unittest
{
    alias throws!parseTemplateTypeArg invalid;
    static assert(invalid("Z")); // not a targ
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a TemplateArg.
private bool isTemplateArg(string man) pure nothrow
{
    return man.length &&
        (man[0] == 'T' || man[0] == 'V' || man[0] == 'S');
}


/***************************************
Parses the string $(D man) as a mangled template type argument and
returns a $(D TemplateArgument) object representing the type.

--------------------
TemplateArg:
    T Type
--------------------
 */
private Demangle!(TemplateArgument)
    parseTemplateTypeArg(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "T"), "not a template type argument", rem);
    rem = rem[1 .. $];

    // Simply extract a type.
    auto type = parseType(rem);
    rem = rem[type.mangle.length .. $];

    // Compose a TemplateArgument object.
    TemplateArgument targ;
    targ.kind = TemplateArgument.Kind.TYPE;
    targ.type = type.content;

    return typeof(return)(man[0 .. $ - rem.length], targ);
}

unittest
{
    enum dem1 = parseTemplateTypeArg("TiZ");
    static assert(dem1.mangle == "Ti");
    static assert(toString(dem1.content) == "int");

    alias throws!parseTemplateTypeArg invalid;
    static assert(invalid("TZ")); // no type
    static assert(invalid("Vii42")); // not type
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled template value argument and
returns a $(D TemplateArgument) object representing the value.

--------------------
TemplateArg:
    V Type Value
--------------------
 */
private Demangle!(TemplateArgument)
    parseTemplateValueArg(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "V"), "not a template value argument", rem);
    rem = rem[1 .. $];

    // Extract the type and value of the argument. The type gives the
    // value an explicit type (values don't have explicit type info).
    auto mtype = parseType(rem);
    auto type = mtype.content;
    rem = rem[mtype.mangle.length .. $];

    auto mval = parseValue(rem);
    auto val = mval.content;
    rem = rem[mval.mangle.length .. $];

    // Associative arrays should have been parsed as static arrays.
    if (type.kind == Type.Kind.AARRAY)
        val.kind = Literal.Kind.AARRAY;

    // Compose a TemplateArgument object.
    TemplateArgument targ;
    targ.kind  = TemplateArgument.Kind.VALUE;
    targ.type  = type;
    targ.value = val;

    return typeof(return)(man[0 .. $ - rem.length], targ);
}

unittest
{
    enum dem1 = parseTemplateValueArg("Vki42Z");
    static assert(dem1.mangle == "Vki42");
    static assert(toString(dem1.content) == "42U");

    enum dem2 = parseTemplateValueArg("VHiiA4i1i2i3i4Z");
    static assert(dem2.mangle == "VHiiA4i1i2i3i4");
    static assert(toString(dem2.content) == "[ 1: 2, 3: 4 ]");

    alias throws!parseTemplateValueArg invalid;
    static assert(invalid("V42")); // no type
    static assert(invalid("Vxi")); // no value
    static assert(invalid("S3std")); // not value
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled template symbol argument and
returns a $(D TemplateArgument) object representing the symbol.

BUGS:
  $(BUGZILLA 3043) must be fixed.

--------------------
TemplateArg:
    S TemplateSymbolArg

TemplateSymbolArg:
    QualifiedName
    M LName
--------------------
 */
private Demangle!(TemplateArgument)
    parseTemplateSymbolArg(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "S"), "not a template symbol argument", rem);
    rem = rem[1 .. $];

    /* A symbol argument is coded to a QualifiedName, or an LName
     * preceded by a letter 'M' (Bugzilla 3043).
     */
    Symbol sym;

    if (startsWith(rem, "M"))
    {
        rem = rem[1 .. $];

        // Extract the mangled name of the symbol.
        auto rawname = parseLName(rem);
        rem = rem[rawname.mangle.length .. $];

        /* Try to demangle the raw mangled name. If it is not a valid
         * mangled name, then use the raw name (not an error).
         */
        sym = rawname.content;

        if (isMangledName(sym.name))
        {
            try
            {
                sym = finish!parseMangledName(sym.name);
            }
            catch {}
        }
        else if (isCppMangledName(sym.name))
        {
            try
            {
                sym = finish!parseCppMangledName(sym.name);
            }
            catch {}
        }
    }
    else
    {
        // a fully qualified name
        auto qname = parseQualifiedName(rem);
        rem = rem[qname.mangle.length .. $];
        sym = qname.content;
    }

    // Compose a TemplateArgument object.
    TemplateArgument targ;
    targ.kind   = TemplateArgument.Kind.SYMBOL;
    targ.symbol = sym;

    return typeof(return)(man[0 .. $ - rem.length], targ);
}

unittest
{
    enum dem1 = parseTemplateArg("S3std4mathZ");
    static assert(dem1.mangle == "S3std4math");
    static assert(toString(dem1.content) == "std.math");

    enum dem2 = parseTemplateArg("SM15_D3std4math2PIe");
    static assert(dem2.mangle == "SM15_D3std4math2PIe");
    static assert(toString(dem2.content) == "real std.math.PI");

    enum dem3 = parseTemplateArg("SM13_ZN4IFoo3fooE");
    static assert(dem3.mangle == "SM13_ZN4IFoo3fooE");
    static assert(toString(dem3.content) == "IFoo.foo");

    enum dem4 = parseTemplateArg("SM6__Dabc");
    static assert(dem4.mangle == "SM6__Dabc");
    static assert(toString(dem4.content) == "__Dabc");

    static assert(throws!parseTemplateArg("SiZ")); // not a symbol
    static assert(throws!parseTemplateArg("")); // empty
}


/***************************************
Parses the string $(D man) as a special symbol name and returns a
$(D Symbol) object representing that symbol.

--------------------
SpecialSymbol:
    main
--------------------
 */
private Demangle!(Symbol) parseSpecialSymbol(string man) pure
{
    string rem = man;
    expect(isSpecialSymbol(rem), "not a special symbol", rem);

    const id = span!(isAsciiAlpha)(rem);
    rem = rem[id.length .. $];

    // Compose a Symbol object.
    Symbol sym;
    sym.kind = Symbol.Kind.IDENTIFIER;
    sym.name = id;

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseSpecialSymbol("main3Foo");
    static assert(dem1.mangle == "main");
    static assert(dem1.content.name == "main");

    alias throws!parseSpecialSymbol invalid;
    static assert(invalid("foo"));
    static assert(invalid("42"));
    static assert(invalid(""));
}

// Returns true if the string man is expected to be a SpecialSymbol.
private bool isSpecialSymbol(string man) pure nothrow
{
    switch (span!(isAsciiAlpha)(man))
    {
        case "main": return  true;
        default    : return false;
    }
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Literal value
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a mangled constant value and returns a
$(D Literal) object representing the value.

--------------------
Value:
    n
    i Number                // positive integer (Bugzilla #3029)
    i N Number              // negative integer
    e HexFloat
    c HexFloat c HexFloat
    A Number Value...
    a Number _ HexNumber
    w Number _ HexNumber
    d Number _ HexNumber
    S Number Value...       // struct literal
--------------------
 */
private Demangle!(Literal) parseValue(string man) pure
{
    enum NULL = Literal(Literal.Kind.NULL);

    switch (man.length ? man[0] : char.init)
    {
        case 'i': return parseNumericLiteral(man);
        case 'e': return parseFloatLiteral(man);
        case 'c': return parseComplexLiteral(man);
        case 'A': return parseArrayLiteral(man);
        case 'S': return parseStructLiteral(man);
        case 'a', 'w', 'd':
            return parseStringLiteral(man);
        case 'n':
            return typeof(return)(man[0 .. 1], NULL);

        // [workaround] Bugzilla #3029
        case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'N':
            return parseBareNumericLiteral(man);

        default:
            error("not a literal value", man);
            assert(0);
    }
}

unittest
{
    enum dem1 = parseValue("n");
    static assert(dem1.mangle == "n");
    static assert(toString(dem1.content) == "null");

    static assert(throws!parseValue("Z")); // not value
    static assert(throws!parseValue("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled integral constant value and
returns a $(D Literal) object representing the value.

--------------------
NumericLiteral:
    i Number
    i N Number
--------------------

BUG:
  Bugzilla #3029 must be fixed.
 */
private Demangle!(Literal) parseNumericLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "i"), "not a numeric literal", rem);
    rem = rem[1 .. $];

    auto bare = parseBareNumericLiteral(man[1 .. $]);
    rem = rem[bare.mangle.length .. $];

    return typeof(return)(man[0 .. $ - rem.length], bare.content);
}

// [internal] NumericLiteral without the prefix 'i'
private Demangle!(Literal) parseBareNumericLiteral(string man) pure
{
    string rem = man;

    // Extract the sign and digits. A sign is coded to 'N'.
    bool neg;

    if (startsWith(rem, "N"))
    {
        rem = rem[1 .. $];
        neg = true;
    }

    auto num = parseNumber(rem);
    rem = rem[num.mangle.length .. $];

    // Huge unsigned numbers are really coded as negative numbers, so
    // we can use toInt without fear of signed integer overflow.
    const val = toInt((neg ? "-" : "") ~ num.content);

    // Compose a Literal object.
    Literal lit;
    lit.kind    = Literal.Kind.INTEGER;
    lit.integer = cast(uintmax_t) val;

    return typeof(return)(man[0 .. $ - rem.length], lit);
}

unittest
{
    enum dem1 = parseValue("i42Z");
    static assert(dem1.mangle == "i42");
    static assert(dem1.content.integer == 42);

    enum dem2 = parseValue("iN42Z");
    static assert(dem2.mangle == "iN42");
    static assert(dem2.content.integer == cast(uintmax_t) -42);

    enum dem3 = parseValue("i0");
    static assert(dem3.mangle == "i0");
    static assert(dem3.content.integer == 0);

    alias throws!parseNumericLiteral invalid;
    static assert(invalid("42")); // needs prefix
    static assert(invalid("Z")); // not an integer
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled floating point constant value
and returns a $(D Literal) object representing the value.

--------------------
FloatLiteral:
    e HexFloat
--------------------
 */
private Demangle!(Literal) parseFloatLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "e"), "not a floating point literal", rem);
    rem = rem[1 .. $];

    // Floating point values are coded in hexadecimal format (e.g.
    // 1FFFP42, which represents 0x1.FFFp42).
    auto xf = parseHexFloat(rem);
    rem = rem[xf.mangle.length .. $];

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.FLOAT;
    val.re   = xf.content;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("e1FFFP42Z");
    static assert(dem1.mangle == "e1FFFP42");
    static assert(dem1.content.re == 0x1.FFFp42L);

    enum dem2 = parseValue("eN1PN1076");
    static assert(dem2.mangle == "eN1PN1076");
    static assert(dem2.content.re == -0x1p-1076L);

    enum dem3 = parseValue("eNINFI");
    static assert(dem3.mangle == "eNINF");
    static assert(dem3.content.re == -real.infinity);

    alias throws!parseFloatLiteral invalid;
    static assert(invalid("e0")); // no HexFloat
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled complex constant value and
returns a $(D Literal) object representing the value.

--------------------
ComplexLiteral:
    c HexFloat c HexFloat
--------------------
 */
private Demangle!(Literal) parseComplexLiteral(string man) pure
{
    string rem = man;

    // Extract re and im. Each of them is prefixed by a letter 'c'.
    real[] reim;

    foreach (i; 0 .. 2)
    {
        expect(startsWith(rem, "c"), "not a complex literal", rem);
        rem = rem[1 .. $];

        auto xf = parseHexFloat(rem);
        rem   = rem[xf.mangle.length .. $];
        reim ~= xf.content;
    }
    assert(reim.length == 2);

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.COMPLEX;
    val.re   = reim[0];
    val.im   = reim[1];

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("c12P3cN14PN5Z");
    static assert(dem1.mangle == "c12P3cN14PN5");
    static assert(toString(dem1.content) == "0x1.2p3 - 0x1.4p-5i");

    alias throws!parseComplexLiteral invalid;
    static assert(invalid("c0P0")); // no im
    static assert(invalid("cc0P0")); // no re
    static assert(invalid("")); // empty
}


/*
Parses the string $(D man) as a hex-mangled floating point value and
returns the $(D real) value.

This function is used by parseFloatLiteral and parseComplexLiteral.

--------------------
HexFloat:
    NAN
    INF
    NINF
    N HexDigits P Exponent  // negative
    HexDigits P Exponent    // positive

Exponent:
    N Number                // negative
    Number                  // positive
--------------------
 */
private Demangle!(real) parseHexFloat(string man) pure
{
    string rem = man;
    real val;

    // Deal with special values.
    if (startsWith(rem, "NAN"))
    {
        rem = rem[3 .. $];
        val = real.nan;
    }
    else if (startsWith(rem, "INF"))
    {
        rem = rem[3 .. $];
        val = +real.infinity;
    }
    else if (startsWith(rem, "NINF"))
    {
        rem = rem[4 .. $];
        val = -real.infinity;
    }
    // Otherwise it must be a usual finite real number.
    else
    {
        /* First build a hexadecimal string representing the value.
         * Then convert it to a real value.
         */
        string str;

        // sign
        if (startsWith(rem, "N"))
        {
            rem  = rem[1 .. $];
            str ~= "-";
        }
        str ~= "0x";

        /* Parse the mantissa part. It's a series of HexDigits. The
         * first HexDigit is the integer part (almost always 1), and
         * the rest is the fraction part.
         */
        auto mant = parseHexNumber(rem);
        rem = rem[mant.mangle.length .. $];

        // the integer part
        str ~= mant.content[0];

        // the fraction part (can be empty)
        if (mant.content.length > 1)
            str ~= "." ~ mant.content[1 .. $];

        /* Parse the exponent part. It's just a BareNumericLiteral
         * preceded by a letter 'P'.
         */
        expect(startsWith(rem, "P"), "exponent part expected", rem);
        rem = rem[1 .. $];

        auto exp = parseBareNumericLiteral(rem);
        rem = rem[exp.mangle.length .. $];

        str ~= "p";
        if (startsWith(exp.mangle, "N"))
            str ~= toString(cast(intmax_t) exp.content.integer);
        else
            str ~= toString(exp.content.integer);

        // Now str should be a valid hex float string.
        val = toReal(str);
    }

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseHexFloat("1AFP10Z");
    static assert(dem1.mangle == "1AFP10");
    static assert(dem1.content == 0x1.AFp10L);

    enum dem2 = parseHexFloat("N1AFPN10Z");
    static assert(dem2.mangle == "N1AFPN10");
    static assert(dem2.content == -0x1.AFp-10L);

    enum dem3 = parseHexFloat("NANZ");
    static assert(dem3.mangle == "NAN");
    static assert(dem3.content !<>= 0);

    enum dem4 = parseHexFloat("INFZ");
    static assert(dem4.mangle == "INF");
    static assert(dem4.content == +real.infinity);

    enum dem5 = parseHexFloat("NINFZ");
    static assert(dem5.mangle == "NINF");
    static assert(dem5.content == -real.infinity);

    alias throws!parseHexFloat invalid;
    static assert(invalid("1AFP")); // no exp
    static assert(invalid("P42")); // no mantissa
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled array literal and returns a
$(D Literal) object representing the array.

--------------------
ArrayLiteral:
    A LValues
--------------------
 */
private Demangle!(Literal) parseArrayLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "A"), "not an array", rem);
    rem = rem[1 .. $];

    auto items = parseLValues(rem);
    rem = rem[items.mangle.length .. $];

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.ARRAY;
    val.next = items.content;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("A3i1i2i3Z");
    static assert(dem1.mangle == "A3i1i2i3");
    static assert(toString(dem1.content) == "[ 1, 2, 3 ]");

    enum dem2 = parseValue("A0");
    static assert(dem2.mangle == "A0");
    static assert(length(dem2.content.next) == 0);

    alias throws!parseArrayLiteral invalid;
    static assert(invalid("AZ")); // no dim
    static assert(invalid("A1Z")); // no elm
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled struct literal and returns a
$(D Literal) object representing the struct value.

--------------------
StructLiteral:
    S LValues
--------------------
 */
private Demangle!(Literal) parseStructLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "S"), "not a struct", rem);
    rem = rem[1 .. $];

    auto items = parseLValues(rem);
    rem = rem[items.mangle.length .. $];

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.STRUCT;
    val.next = items.content;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("S3i1i2i3Z");
    static assert(dem1.mangle == "S3i1i2i3");
    static assert(toString(dem1.content) == "struct(1, 2, 3)");

    enum dem2 = parseValue("S0");
    static assert(dem2.mangle == "S0");
    static assert(length(dem2.content.next) == 0);

    alias throws!parseStructLiteral invalid;
    static assert(invalid("SZ")); // no dim
    static assert(invalid("S1Z")); // no elm
    static assert(invalid("")); // empty
}


/*
Parses the string $(D man) as zero or more consequent Literals and
returns an array of the literals.

--------------------
LValues:
    Number Value*
--------------------
 */
private Demangle!(Literal[]) parseLValues(string man) pure
{
    string rem = man;

    // the number of items expected
    auto dim = parseNumber(rem);
    rem = rem[dim.mangle.length .. $];

    // Extract exactly dim items.
    Literal[] items;

    foreach (i; 0 .. toSize(dim.content))
    {
        auto item = parseValue(rem);
        rem    = rem[item.mangle.length .. $];
        items ~= item.content;
    }
    return typeof(return)(man[0 .. $ - rem.length], items);
}


/***************************************
Parses the string $(D man) as a mangled string literal and returns a
$(D Literal) object representing the string.

--------------------
StringLiteral:
    a Number _ HexDigits    // UTF-8 string
    w Number _ HexDigits    // UTF-16 string (in UTF-8)
    d Number _ HexDigits    // UTF-32 string (in UTF-8)
--------------------
 */
private Demangle!(Literal) parseStringLiteral(string man) pure
{
    string rem = man;

    /* Detect the string suffix. Note that the UTF-8 suffix 'c' is
     * coded to 'a'.
     */
    string suffix;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'a': suffix = "c"; break; // UTF-8
        case 'w': suffix = "w"; break; // UTF-16
        case 'd': suffix = "d"; break; // UTF-32

        default:
            error("not a string literal", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    // the length of the string in UTF-8 bytes
    auto num = parseNumber(rem);
    rem = rem[num.mangle.length .. $];
    const len = toSize(num.content);

    expect(startsWith(rem, "_"), "delimiter '_' expected", rem);
    rem = rem[1 .. $];

    /* The string is stored as a UTF-8 string coded in the lowercase
     * base-16 (hexadecimal) format.
     */
    static bool isLowerHexDigit(char ch) pure nothrow
    {
        return isDigit(ch) || ('a' <= ch && ch <= 'f');
    }

    // The length may be too big v.s. the input string.
    expect(len <= (rem.length + 1) / 2, "string out of input", rem);

    // Extract valid base-16 characters.
    string str = span!(isLowerHexDigit)(rem[0 .. 2 * len]);
    expect(str.length == 2 * len, "badly mangled string literal", rem);
    rem = rem[str.length .. $];

    str = decodeBase16String(str);

    // Compose a Literal object.
    Literal val;
    val.kind   = Literal.Kind.STRING;
    val.text   = str;
    val.suffix = suffix;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("a3_e381a7Z");
    static assert(dem1.mangle == "a3_e381a7");
    static assert(dem1.content.text   == x"e3 81 a7");
    static assert(dem1.content.suffix == "c");

    enum dem2 = parseValue("w0_");
    static assert(dem2.mangle == "w0_");
    static assert(dem2.content.text.length == 0);
    static assert(dem2.content.suffix == "w");

    alias throws!parseStringLiteral invalid;
    static assert(invalid("a_")); // no len
    static assert(invalid("a120")); // no _
    static assert(invalid("")); // empty
}


/*
Decodes the UTF-8 string encoded to lowercase hexadecimal digits byte
by byte.
 */
private string decodeBase16String(string x) pure nothrow
in
{
    assert(x.length % 2 == 0);
}
body
{
    static ubyte hexToNibble(char ch) pure nothrow
    {
        if ('0' <= ch && ch <= '9')
            return cast(ubyte) (ch - '0');
        if ('a' <= ch && ch <= 'f')
            return cast(ubyte) (ch - 'a' + 10);
        assert(0);
    }

    string s = "";

    for (size_t i = 0; i < x.length; )
    {
        const hi = hexToNibble(x[i++]);
        const lo = hexToNibble(x[i++]);

        s ~= cast(char) ((hi << 4) | lo);
    }
    return s;
}

unittest
{
    static assert(decodeBase16String("") == "");
    static assert(decodeBase16String("5a5b5c") == x"5a5b5c");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Mangled Name
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a mangled D symbol name and returns a
$(D Symbol) object representing the symbol (varaible or function).

--------------------
MangledName:
    _D QualifiedName Type
    _D QualifiedName M Type
--------------------
 */
private Demangle!(Symbol) parseMangledName(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "_D"), "not a D mangled name", rem);
    rem = rem[2 .. $];

    // Extract the fully qualified name. Type is handled by
    // parseQualifiedName.
    auto qname = parseQualifiedName(rem);
    rem = rem[qname.mangle.length .. $];

    return typeof(return)(man[0 .. $ - rem.length], qname.content);
}

unittest
{
    enum dem1 = parseMangledName("_D3std4math2PIe");
    static assert(dem1.mangle == "_D3std4math2PIe");
    static assert(toString(dem1.content) == "real std.math.PI");

    enum dem2 = parseMangledName("_D4core4stdc6strcpyUNbPaxPaZPa");
    static assert(dem2.mangle == "_D4core4stdc6strcpyUNbPaxPaZPa");
    static assert(toString(dem2.content) ==
            "extern(C) nothrow "
            "char* core.stdc.strcpy(char*, const(char*))");

    enum dem3 = parseMangledName("_Dmain");
    static assert(dem3.mangle == "_Dmain");
    static assert(dem3.content.name == "main");

    alias throws!parseMangledName invalid;
    static assert(invalid("_D")); // out of input
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a MangledName.
private bool isMangledName(string man) pure nothrow
{
    return startsWith(man, "_D");
}


//===================================================================//
// Limited support for C++ mangled names
//===================================================================//

/***************************************
Parses the string $(D man) as a C++ mangled symbol name and returns a
$(D Symbol) object representing the symbol.

BUGS:
Incomplete.

Reference:
http://www.codesourcery.com/public/cxx-abi/abi.html

--------------------
MangledName:
    _Z Encoding

Encoding:
    Name BareFunctionType

Name:
    N [CVRQualifiers] QualifiedName E
    LName

BareFunctionType:
    Type
    Type BareFunctionType

CVRQualifiers:
    [r] [V] [K]
--------------------
 */
private Demangle!(Symbol) parseCppMangledName(string man) pure
{
    string rem = man;
    Symbol sym;

    // expect "_Z"
    expect(startsWith(rem, "_Z"), "not a C++ mangled name", rem);
    rem = rem[2 .. $];

    if (startsWith(rem, "N"))
    {
        rem = rem[1 .. $];

        // Ignore CVR qualifiers.
        if (startsWith(rem, "r")) rem = rem[1 .. $];
        if (startsWith(rem, "V")) rem = rem[1 .. $];
        if (startsWith(rem, "K")) rem = rem[1 .. $];

        auto qname = parseQualifiedName(rem);
        rem = rem[qname.mangle.length .. $];
        sym = qname.content;

        expect(startsWith(rem, "E"), "'E' expected", rem);
        rem = rem[1 .. $];

        // BareFunctionType
        if (rem.length)
            throw new Exception("not implemented");
    }
    else
    {
        auto name = parseLName(rem);
        rem = rem[name.mangle.length .. $];
        sym = name.content;
    }

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseCppMangledName("_ZN1C3fooE");
    static assert(dem1.mangle == "_ZN1C3fooE");
    static assert(toString(dem1.content) == "C.foo");

    alias throws!parseCppMangledName invalid;
    static assert(invalid("_D3std4math3sinFNaNbeZe")); // not C++
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a C++ mangled name.
private bool isCppMangledName(string man) pure nothrow
{
    return startsWith(man, "_Z");
}


//===================================================================//
// CTFE-friendly reflected information
//===================================================================//

// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Type information
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D Type) object represents a type available in D.

There are various kinds of types in D: basic types (such as $(D int)),
array types, user-defined types, etc. The $(D kind) field indicates
which kind of type is represented by a $(D Type) object, and other
fields hold more detailed information. For example, the $(D storage)
field is the storage class applied to the type, and the $(D next) field
is an array of other types referenced by the type.

Example:

Construct a $(D Type) object for $(D immutable(char)[42]). This example
is executable at compile time.
--------------------
// immutable(char)
Type chr;
chr.kind = Type.Kind.CHAR;
chr.storage = StorageClass.IMMUTABLE;

// chr[42]
Type str;
str.kind = Type.Kind.SARRAY;
str.next = [ chr ];
str.length = 42;

assert(toString(str) == "immutable(char)[42]");
--------------------
 */
struct Type
{
    /**
     * The $(D kind) field indicates which _kind of type is
     * represented by this object. The value can be one of these:
     */
    enum Kind
    {
        /**
         * No type. No other fields are used.
         */
        NONE,

        /**
         * Basic types.
         */
        VOID,
        BYTE,    /// ditto
        UBYTE,   /// ditto
        SHORT,   /// ditto
        USHORT,  /// ditto
        INT,     /// ditto
        UINT,    /// ditto
        LONG,    /// ditto
        ULONG,   /// ditto
        CENT,    /// ditto
        UCENT,   /// ditto
        FLOAT,   /// ditto
        DOUBLE,  /// ditto
        REAL,    /// ditto
        IFLOAT,  /// ditto
        IDOUBLE, /// ditto
        IREAL,   /// ditto
        CFLOAT,  /// ditto
        CDOUBLE, /// ditto
        CREAL,   /// ditto
        BOOL,    /// ditto
        CHAR,    /// ditto
        WCHAR,   /// ditto
        DCHAR,   /// ditto

        /**
         * Dynamic and static array types. The first element of the
         * $(D next) field, $(D next[0]), is the element type and the
         * $(D length) field is the length of the static array.
         */
        ARRAY,
        SARRAY, /// ditto

        /**
         * Associative array type. The first element of the $(D next)
         * field, $(D next[0]), is the key type and the second one,
         * $(D next[1]), is the value type.
         */
        AARRAY,

        /**
         * Pointer type. The first element of the $(D next) field,
         * $(D next[0]), is the referenced type.
         */
        POINTER,

        /**
         * Function and delegate types. Note that a function type is
         * not a function pointer type. A function pointer type is a
         * pointer type that references a function type.
         *
         * $(UL
         *  $(LI The first element of the $(D next) field,
         *     $(D next[0]), is the return type.)
         *  $(LI The rest, $(D next[1 .. $]), are the parameter types.)
         *  $(LI The $(D attributes) field is the function attributes.
         *     It's zero or a bitwise-OR of some $(D FunctionAttribute
         *     ) member values.)
         *  $(LI The $(D linkage) field is the calling convention.)
         *  $(LI The $(D variadic) field indicates whether the
         *     function is variadic.)
         *  $(LI The $(D needThis) field is $(D true) if the function
         *     is a member function or a nested function.)
         * )
         */
        FUNCTION,
        DELEGATE, /// ditto

        /**
         * User-defined types. The $(D symbol) field is the declared
         * symbol of the type. The $(D next) field is an array of the
         * base types (if any).
         */
        IDENT,
        CLASS,   /// ditto
        STRUCT,  /// ditto
        ENUM,    /// ditto
        TYPEDEF, /// ditto

        /**
         * Type tuple. The $(D next) field is an array of the types in
         * the tuple. The $(D storage) field is not used.
         */
        TUPLE,
    }
    Kind kind; /// ditto

    /**
     * The _storage class applied to this type. It's zero or a
     * bitwise-OR of some $(D StorageClass) member values. This field
     * is common to all type kinds but $(D NONE) and $(D TUPLE).
     */
    StorageClass storage;

    /**
     * Types referenced by this type.
     */
    Type[] next;

    /**
     * The dimension of a static array.
     */
    size_t length;

    /**
     * Information about a function or delegate type.
     */
    FunctionAttribute attributes;
    Linkage              linkage; /// ditto
    Variadic            variadic; /// ditto
    bool                needThis; /// ditto

    /**
     * The _symbol, if any, of this type.
     */
    Symbol[] symbol;
}


/**
Ditto
 */
bool equal(in Type ta, in Type tb)
{
    alias Type.Kind T;

    /* General checks.
     */
    if (ta.kind != tb.kind)
        return false;

    // none is none
    if (ta.kind == T.NONE)
        return true;

    // storage class must match
    if (ta.storage != tb.storage)
        return false;

    // symbol must match (if any)
    if (ta.symbol.length || tb.symbol.length)
    {
        if (ta.symbol.length != tb.symbol.length)
            return false;

        if (!equal(ta.symbol[0], tb.symbol[0]))
            return false;
    }

    /* Kind-specific checks
     */
    switch (ta.kind)
    {
        case T.FUNCTION, T.DELEGATE:
        {
            // Function modifiers must match.
            if (ta.attributes != tb.attributes ||
                ta.linkage    != tb.linkage    ||
                ta.variadic   != tb.variadic)
            {
                return false;
            }
            break;
        }

        case T.SARRAY:
        {
            // dimensions must match
            if (ta.length != tb.length)
                return false;
            break;
        }

        case T.ARRAY, T.AARRAY, T.POINTER,
             T.CLASS, T.STRUCT, T.ENUM, T.TYPEDEF,
             T.TUPLE:
            break;

        // No more test is needed
        default:
            return true;
    }

    /* Check for the referenced types.
     */
    if (ta.next.length != tb.next.length)
        return false;

    foreach (i; 0 .. ta.next.length)
    {
        if (!equal(ta.next[i], tb.next[i]))
            return false;
    }

    // Congratulations!
    return true;
}

unittest
{
    alias Type.Kind    T;
    alias StorageClass STC;

    enum t1 = Type(T.NONE);
    static assert(equal(t1, t1));

    enum t2a = Type(T.INT);
    enum t2b = Type(T.INT, STC.CONST);
    enum t2c = Type(T.SHORT);
    static assert( equal(t2a, t2a));
    static assert( equal(t2b, t2b));
    static assert( equal(t2c, t2c));
    static assert(!equal(t2a, t2b));
    static assert(!equal(t2b, t2c));
    static assert(!equal(t2c, t2a));

    enum t3a = Type(T.ARRAY, STC.NONE, [ Type(T.INT) ]);
    enum t3b = Type(T.SARRAY, STC.NONE, [ Type(T.INT) ], 4);
    static assert( equal(t3a, t3a));
    static assert( equal(t3b, t3b));
    static assert(!equal(t3a, t3b));
}


/**
Ditto
 */
string toString(Type ty)
{
    alias Type.Kind T;

    switch (ty.kind)
    {
        case T.NONE:
            return null;

        // String representation of function (delegate) type is
        // different from that of other types.
        case T.FUNCTION, T.DELEGATE:
            return toString_function(ty);

        // So is tuple.
        case T.TUPLE:
            return toString_tuple(ty);

        default:
            return appendStorageClass(
                    toString_withoutStoc(ty), ty.storage);
    }
}

unittest
{
    alias StorageClass STC;

    enum t1 = Type(Type.Kind.INT, STC.CONST | STC.REF);
    static assert(toString(t1) == "ref const(int)");

    enum t2 = Type(Type.Kind.INT, STC.SCOPE | STC.LAZY | STC.CONST);
    static assert(toString(t2) == "lazy scope const(int)");
}


/*
Converts a type $(D ty) to its string representation ignoring the
storage class. $(D ty) cannot be neither $(D NONE), $(D FUNCTION),
$(D DELEGATE) nor $(D TUPLE).
 */
private string toString_withoutStoc(Type ty)
in
{
    assert(ty.kind != Type.Kind.NONE);
}
body
{
    alias Type.Kind T;

    /* Try basic types.
     */
    static immutable string[T.max + 1] BASIC_TYPE_NAME =
        // XXX: Bugzilla #3026 must be fixed
    [
        T.VOID  :   "void",
        T.BYTE  :   "byte", T.UBYTE  :   "ubyte",
        T.SHORT :  "short", T.USHORT :  "ushort",
        T.INT   :    "int", T.UINT   :    "uint",
        T.LONG  :   "long", T.ULONG  :   "ulong",
        T.CENT  :   "cent", T.UCENT  :   "ucent", // TBD
        T.FLOAT :  "float", T.IFLOAT :  "ifloat", T.CFLOAT :  "cfloat",
        T.DOUBLE: "double", T.IDOUBLE: "idouble", T.CDOUBLE: "cdouble",
        T.REAL  :   "real", T.IREAL  :   "ireal", T.CREAL  :   "creal",
        T.BOOL  :   "bool",
        T.CHAR  :   "char", T.WCHAR  :   "wchar", T.DCHAR  :   "dchar",
    ];
    if (BASIC_TYPE_NAME[ty.kind])
        return BASIC_TYPE_NAME[ty.kind];

    /* More complex types
     */
    switch (ty.kind)
    {
        case T.ARRAY, T.SARRAY: return toString_array(ty);
        case T.AARRAY : return toString_assocArray(ty);
        case T.POINTER: return toString_pointer(ty);

        // User-defined types
        case T.IDENT  : return toString(ty.symbol[0]);
        case T.CLASS  : return   "class " ~ toString(ty.symbol[0]);
        case T.STRUCT : return  "struct " ~ toString(ty.symbol[0]);
        case T.ENUM   : return    "enum " ~ toString(ty.symbol[0]);
        case T.TYPEDEF: return "typedef " ~ toString(ty.symbol[0]);

        default: assert(0); // does not reach
    }
}

unittest
{
    alias    Type.Kind T;
    alias StorageClass STC;
    alias  Symbol.Kind S;

    enum t1 = Type(T.REAL, STC.CONST);
    static assert(toString_withoutStoc(t1) == "real"); // w/o const

    enum t2 = makeStruct!(Type, "kind", "symbol")(
            T.CLASS, [ Symbol(S.IDENTIFIER, "MyClass") ]);
    static assert(toString_withoutStoc(t2) == "class MyClass");
}


/*
Converts a dynamic/static array type $(D ty) into its string
representation. This function rewrites immutable(char)[] to string;
wstring and dstring as well. The direct storage class is ignored.
 */
private string toString_array(Type ty)
in
{
    assert(ty.kind == Type.Kind.ARRAY ||
           ty.kind == Type.Kind.SARRAY);
    assert(ty.next.length == 1);
}
body
{
    alias    Type.Kind T;
    alias StorageClass STC;

    auto next = ty.next[0];

    if (ty.kind == Type.Kind.SARRAY)
    {
        // static array
        uintmax_t dim = ty.length;
        return toString(next) ~ "[" ~ toString(dim) ~ "]";
    }
    else
    {
        // dynamic array
        enum
        {
            Timmchar = Type(T.CHAR, STC.IMMUTABLE),
            Timmwchar = Type(T.WCHAR, STC.IMMUTABLE),
            Timmdchar = Type(T.DCHAR, STC.IMMUTABLE),
        }

        if (equal(next, Timmchar)) return "string";
        if (equal(next, Timmwchar)) return "wstring";
        if (equal(next, Timmdchar)) return "dstring";

        return toString(next) ~ "[]";
    }
}

unittest
{
    alias    Type.Kind T;
    alias StorageClass STC;

    enum t1 = Type(T.ARRAY, STC.NONE,
            [ Type(T.INT, STC.SHARED) ]);
    static assert(toString(t1) == "shared(int)[]");

    enum t2 = Type(T.SARRAY, STC.NONE,
            [ Type(T.SHORT, STC.CONST) ], 42);
    static assert(toString(t2) == "const(short)[42]");

    // special cases
    enum tcstr = Type(T.ARRAY, STC.CONST,
            [ Type(T.CHAR, STC.IMMUTABLE) ]);
    static assert(toString(tcstr) == "const(string)");

    enum twstr = Type(T.ARRAY, STC.CONST,
            [ Type(T.WCHAR, STC.IMMUTABLE) ]);
    static assert(toString(twstr) == "const(wstring)");

    enum tdstr = Type(T.ARRAY, STC.CONST,
            [ Type(T.DCHAR, STC.IMMUTABLE) ]);
    static assert(toString(tdstr) == "const(dstring)");
}


/*
Converts an associative array type $(D ty) into its string
representation. The direct storage class is ignored.
 */
private string toString_assocArray(Type ty)
in
{
    assert(ty.kind == Type.Kind.AARRAY);
    assert(ty.next.length == 2);
}
body
{
    const kname = toString(ty.next[0]);
    const vname = toString(ty.next[1]);
    return vname ~ "[" ~ kname ~ "]";
}

unittest
{
    alias    Type.Kind T;
    alias StorageClass STC;

    enum t1 = Type(T.AARRAY, STC.CONST,
            [ Type(T.CHAR), Type(T.REAL) ]);
    static assert(toString(t1) == "const(real[char])");
}


/*
Converts a pointer type $(D ty) into its string representation. The
direct storage class is ignored.
 */
private string toString_pointer(Type ty)
in
{
    assert(ty.kind == Type.Kind.POINTER);
}
body
{
    Type next = ty.next[0];

    // function pointer has its own syntax
    if (next.kind == Type.Kind.FUNCTION)
    {
        next.symbol =
            [ Symbol(Symbol.Kind.IDENTIFIER, "function") ];
        return toString(next);
    }

    // usual pointer syntax
    return toString(next) ~ "*";
}

unittest
{
    alias         Type.Kind T;
    alias      StorageClass STC;
    alias FunctionAttribute FA;

    enum t1 = Type(T.POINTER, STC.NONE,
            [ Type(T.CHAR, STC.IMMUTABLE) ]);
    static assert(toString(t1) == "immutable(char)*");

    enum t2f = Type(T.FUNCTION, STC.NONE,
                [ Type(T.VOID) ], 0, FA.NOTHROW);
    enum t2 = Type(T.POINTER, STC.NONE, [ t2f ]);
    static assert(toString(t2) == "nothrow void function()");
}


/*
Converts a function (delegate) type $(D ty) into its string
representation. A calling convention comes first, and storage class,
attributes, return type, name (if any), and parameters follow.

Examples:
--------------------
"pure nothrow real(real)"
"const ref int delegate(out int r, in int[] a...)"
"pure nothrow real std.math.pow(real, real)"
--------------------
 */
private string toString_function(Type ty)
in
{
    assert(ty.kind == Type.Kind.FUNCTION ||
           ty.kind == Type.Kind.DELEGATE);
}
body
{
    alias FunctionAttribute FA;
    alias      StorageClass STC;

    // Return type
    auto rtype = toString(ty.next[0]);

    /* Function name, "function" or "delegate". The function name
     * (ty.symbol[0]) is set when this type is used with symbol name;
     * it's also set to "function" when the type is used via a
     * function pointer.
     *
     * It's empty if the type is JUST a function type. "int(int, real)"
     */
    string fun;

    if (ty.symbol)
        fun = toString(ty.symbol[0]);
    else if (ty.kind == Type.Kind.DELEGATE)
        fun = "delegate";

    if (fun.length)
        fun = " " ~ fun; // need a space after the return type

    /* Parameters: join parameter types (which are in next[1 .. $])
     * with ", ". Parameter storage class is handled by toString(Type).
     */
    string params = "";

    foreach (i, pt; ty.next[1 .. $])
    {
        if (i >= 1)
            params ~= ", ";
        params ~= toString(pt);
    }

    // Deal with variadic arguments.
    params = appendVararg(params, ty.variadic);

    // Compose.
    string sig = rtype ~ fun ~ "(" ~ params ~ ")";
    sig = sig.prefixFunction(ty.linkage, ty.storage, ty.attributes);
    return sig;
}

unittest
{
    alias         Type.Kind T;
    alias      StorageClass STC;
    alias FunctionAttribute FA;

    enum t1 = Type(T.FUNCTION, STC.CONST,
        [ Type(T.INT), Type(T.UINT, STC.SCOPE) ],
        0,
        FA.REF | FA.NOTHROW, Linkage.C, Variadic.VARIADIC);
    static assert(toString_function(t1) ==
            "extern(C) const nothrow ref int(scope uint, ...)");

    enum t2 = Type(T.FUNCTION, STC.NONE,
        [ Type(T.REAL), Type(T.REAL) ],
        0,
        FA.PURE | FA.NOTHROW, Linkage.D, Variadic.NO, false,
        [ createSymbol([ "std", "math", "sin" ]) ]);
    static assert(toString_function(t2) ==
            "pure nothrow real std.math.sin(real)");

    enum t3 = Type(T.DELEGATE, STC.NONE,
        [ Type(T.VOID), Type(T.ARRAY, STC.IN, [ Type(T.INT) ]) ],
        0,
        FA.NONE, Linkage.D, Variadic.TYPESAFE);
    static assert(toString_function(t3) ==
            "void delegate(in int[]...)");
}


/*
Converts a TypeTuple $(D ty) into its string representation. This
function does not deal with storage class nor nested tuples.
 */
private string toString_tuple(Type ty)
in
{
    assert(ty.kind == Type.Kind.TUPLE);
    assert(ty.storage == 0, "storage class is undefined for tuple");
}
body
{
    string s = "(";

    if (ty.next) // [workaround] CTFE
    foreach (i, t; ty.next)
    {
        if (i >= 1)
            s ~= ", ";
        s ~= toString(t);
    }
    s ~= ")";
    return s;
}

unittest
{
    alias StorageClass STC;

    enum t1 = Type(Type.Kind.TUPLE);
    static assert(toString_tuple(t1) == "()");

    enum t2 = Type(Type.Kind.TUPLE, STC.NONE,
            [ Type(Type.Kind.BYTE) ]);
    static assert(toString_tuple(t2) == "(byte)");

    enum t3 = Type(Type.Kind.TUPLE, STC.NONE,
            [ Type(Type.Kind.INT), Type(Type.Kind.DCHAR) ]);
    static assert(toString_tuple(t3) == "(int, dchar)");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Literal values
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D Literal) object represents a compile-time constant value.

A compile-time constant value is $(D null), an integer, a floating
point, a complex floating point, an array, an associative array, a
string or a struct. The $(D kind) field indicates which kind of literal
is stored in a $(D Literal) object.

Example:

Construct a complex floating point literal. Floating point values are
converted to hexadecimal strings.
--------------------
auto val = Literal(Literal.Kind.COMPLEX);
val.re = 3.5;
val.im = 0;
val.suffix = "L";
assert(toString(val) == "0x1.Cp1L + 0x0p0Li");
--------------------
*/
struct Literal
{
    /**
     * The $(D kind) field indicates which kind of literal value is
     * represented by this object. The value can be one of these:
     */
    enum Kind
    {
        /**
         * Null. No other fields are used.
         */
        NULL,

        /**
         * Integer. The $(D integer) field holds the integral value
         * as a unsigned integer. The $(D suffix) field holds the
         * integer suffix ($(D U) and/or $(D L)).
         */
        INTEGER,

        /**
         * Real or imaginary. The $(D re) field holds the floating
         * point value. The $(D suffix) field holds the floating point
         * suffix ($(D F) or $(D L); and/or $(D i)).
         */
        FLOAT,

        /**
         * Complex floating point. The $(D re) field holds the real
         * part and the $(D im) field holds the imaginary part. The
         * $(D suffix) field holds the floating point suffix ($(D F)
         * or $(D L)) that is applied to the both parts.
         */
        COMPLEX,

        /**
         * Static array. The $(D next) field is an array of the
         * elements.
         */
        ARRAY,

        /**
         * Associative array. The $(D next) field is an array of keys
         * and values. The keys and values are interleaved, as
         * $(D [ key, value, key, value, ... ]).
         */
        AARRAY,

        /**
         * String. The $(D text) field holds the string in UTF-8. The
         * $(D suffix) field holds the string suffix ($(D c), $(D w)
         * or $(D d)).
         */
        STRING,

        /**
         * Struct. The $(D next) field is an array of the field
         * initializers.
         */
        STRUCT,
    }
    Kind kind; /// Ditto

    /**
     * The value of an _integer literal cast to an unsigned _integer
     * type. Whether the actual value is signed or unsigned is
     * detemined by the $(D suffix) field or external type information.
     */
    uintmax_t integer;

    /**
     * The real and imaginary parts of a floating point value.
     */
    real re;
    real im; /// ditto

    /**
     * A string literal in UTF-8.
     */
    string text;

    /**
     * The _suffix appended to this literal.
     */
    string suffix;

    /**
     * Other literals referenced by this literal.
     */
    Literal[] next;
}


/**
Ditto
 */
bool equal(in Literal va, in Literal vb)
{
    alias Literal.Kind V;

    if (va.kind != vb.kind)
        return false;

    switch (va.kind)
    {
        case V.NULL:
            return true; // both are null

        case V.INTEGER:
            return va.integer == vb.integer && va.suffix == vb.suffix;

        case V.FLOAT:
            return equal(va.re, vb.re) && va.suffix == vb.suffix;

        case V.COMPLEX:
            return equal(va.re, vb.re) && equal(va.im, vb.im) &&
                   va.suffix == vb.suffix;

        case V.STRING:
            return va.text == vb.text && va.suffix == vb.suffix;

        // check for all elements
        case V.ARRAY, V.STRUCT:
        {
            if (va.next.length != vb.next.length)
                return false;

            foreach (i; 0 .. va.next.length)
            {
                if (!equal(va.next[i], vb.next[i]))
                    return false;
            }
            return true;
        }

        // does not reach
        default: assert(0);
    }
}

unittest
{
    alias Literal.Kind V;
    alias makeStruct!(Literal, "kind", "text", "suffix") String;
    alias makeStruct!(Literal, "kind", "next") Next;

    enum v1 = Literal(V.NULL);
    static assert(equal(v1, v1));

    enum v2a = Literal(V.INTEGER,  42);
    enum v2b = Literal(V.INTEGER, -42);
    enum v2c = Literal(V.COMPLEX, 0, real.nan, 0);
    static assert( equal(v2a, v2a));
    static assert( equal(v2b, v2b));
    static assert( equal(v2c, v2c));
    static assert(!equal(v2a, v2b));
    static assert(!equal(v2b, v2c));
    static assert(!equal(v2c, v2a));

    enum v3a = String(V.STRING, "abc", "c");
    enum v3b = String(V.STRING, "abc", "w");
    enum v3c = String(V.STRING, "cba", "");
    static assert( equal(v3a, v3a));
    static assert( equal(v3b, v3b));
    static assert( equal(v3c, v3c));
    static assert(!equal(v3a, v3b));
    static assert(!equal(v3b, v3c));
    static assert(!equal(v3c, v3a));

    enum v4a = Next(V. ARRAY, [ Literal(V.INTEGER, 42) ]);
    enum v4b = Next(V.STRUCT, [ Literal(V.INTEGER, 42) ]);
    static assert( equal(v4a, v4a));
    static assert( equal(v4b, v4b));
    static assert(!equal(v4a, v4b));
}

/*
[internal] a == b or both are NaN
 */
private bool equal(real a, real b) pure nothrow
{
    return a == b || (a !<>= 0 && b !<>= 0);
}

unittest
{
    static assert( equal(1.L, 1.L));
    static assert(!equal(1.L, 2.L));
    static assert( equal(real.nan, real.nan));
    static assert(!equal(1.L, real.nan));
    static assert( equal(real.infinity, real.infinity));
    static assert(!equal(-real.infinity, real.infinity));
}


/**
Ditto
 */
string toString(Literal val, Type ty = Type.init)
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    // Type is unspecified. Use the deduced one.
    if (ty.kind == T.NONE)
        ty = deduceType(val);

    // hub
    switch (val.kind)
    {
        case V.NULL:
            return toString_nullLiteral(ty);

        case V.INTEGER:
            return toString_integer(val, ty);

        case V.FLOAT:
            return toString_float(val, ty);

        case V.COMPLEX:
            return toString_complex(val, ty);

        case V.ARRAY:
            return toString_array(val, ty);

        case V.AARRAY:
            return toString_assocArray(val, ty);

        case V.STRUCT:
            return toString_struct(val, ty);

        case V.STRING:
            return toString_string(val, ty);

        default: assert(0); // does not reach
    }
}


/*
Returns a unary expression string representing a $(D null) of the
specified type $(D ty).
 */
private string toString_nullLiteral(Type ty)
{
    enum Tnull = deduceType(Literal(Literal.Kind.NULL));

    if (equal(ty, Tnull))
        return "null";
    else
        return "cast(" ~ toString(ty) ~ ") null";
}

unittest
{
    alias Type.Kind    T;
    alias StorageClass STC;

    enum t1 = Type(T.POINTER, STC.NONE, [ Type(T.VOID) ]);
    static assert(toString_nullLiteral(t1) == "null");

    enum t2 = Type(T.ARRAY, STC.NONE, [ Type(T.CHAR) ]);
    static assert(toString_nullLiteral(t2) == "cast(char[]) null");

    enum t3 = Type(T.POINTER, STC.NONE, [ Type(T.VOID, STC.CONST) ]);
    static assert(toString_nullLiteral(t3) ==
            "cast(const(void)*) null");
}


/*
Returns a unary expression string representing the integer literal
$(D val) of the type $(D ty).

The result will look like: "cast(short) 1234"
 */
private string toString_integer(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.INTEGER);
}
body
{
    alias Type.Kind T;
    string s;
    bool needcast;

    switch (ty.kind)
    {
        default:
            s = toString(cast(intmax_t) val.integer);
            break;

        case T.UBYTE, T.USHORT, T.UINT, T.ULONG, T.UCENT:
            s = toString(cast(uintmax_t) val.integer);
            break;

        case T.CHAR, T.WCHAR, T.DCHAR:
            return toString_char(val, ty);
    }

    // Integer literal doesn't have storage class.
    if (ty.storage != StorageClass.NONE)
    {
        needcast = true;
    }
    else
    {
        // Try to reduce the cast by appending a suffix.
        switch (ty.kind)
        {
            case T.  INT:            break;
            case T. UINT: s ~= "U" ; break;
            case T. LONG: s ~=  "L"; break;
            case T.ULONG: s ~= "UL"; break;

            // Need explicit convertion.
            default:
                needcast = true;
                break;
        }
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    auto v = Literal(V.INTEGER, 42);
    auto t1 = Type(T.INT);
    auto t2 = Type(T.UINT);
    auto t3 = Type(T.LONG);
    auto t4 = Type(T.ULONG);
    auto t5 = Type(T.USHORT);
    auto t6 = Type(T.REAL);
    assert(toString_integer(v, t1) == "42");
    assert(toString_integer(v, t2) == "42U");
    assert(toString_integer(v, t3) == "42L");
    assert(toString_integer(v, t4) == "42UL");
    assert(toString_integer(v, t5) == "cast(ushort) 42");
    assert(toString_integer(v, t6) == "cast(real) 42");
}


/*
Returns a unary expression string representing the character literal
$(D val) of the type $(D ty).
 */
private string toString_char(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.INTEGER);
    assert(ty.kind == Type.Kind. CHAR ||
           ty.kind == Type.Kind.WCHAR ||
           ty.kind == Type.Kind.DCHAR );
}
body
{
    static immutable byte[0x80] PRINTABLE =
    [
        0x0: 2,
        0x9: 2,2,2,2,2,
        ' ': 1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,
        '0': 1,1,1,1,1,1,1,1,1,1,
        ':': 1,1,1,1,1,1,1,
        'A': 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
        '[': 1,2,1,1,1,1,
        'a': 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
        '{': 1,1,1,1
    ];

    alias Type.Kind T;
    string s;
    bool needsuffix;

    if (val.integer > uint.max)
        throw new Exception("character code overflow");
    const code = cast(uint) val.integer;

    // Some characters are directly representable.
    if (code < 0x80 && PRINTABLE[code])
    {
        auto ch = cast(immutable char) code;
        switch (ch)
        {
            // control characters
            case '\0': s = `\0`; break;
            case '\t': s = `\t`; break;
            case '\n': s = `\n`; break;
            case '\v': s = `\v`; break;
            case '\f': s = `\f`; break;
            case '\r': s = `\r`; break;

            // need escape
            case '\'': s = `\'`; break;
            case '\\': s = `\\`; break; //`

            // direct
            default:
                s = [ cast(immutable char) ch ];
                break;
        }
        needsuffix = true;
    }
    else
    {
        // Represent the character by its Unicode point.
        const hex = toHexString(cast(uintmax_t) code, 8u)[2 .. $];

        switch (ty.kind)
        {
            case T.CHAR:
                s = "\\x" ~ hex[$ - 2 .. $];
                break;

            case T.WCHAR:
                s = "\\u" ~ hex[$ - 4 .. $];
                break;

            case T.DCHAR:
                s = "\\U" ~ hex[$ - 8 .. $];
                break;

            default:
                assert(0);
        }
    }
    s = "'" ~ s ~ "'";

    if (needsuffix)
    {
        switch (ty.kind)
        {
            case T. CHAR:           break;
            case T.WCHAR: s ~= "w"; break;
            case T.DCHAR: s ~= "d"; break;
            default:
                assert(0);
        }
    }

    // Finish.
    if (ty.storage != StorageClass.NONE)
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    auto v1 = Literal(V.INTEGER, 65);
    assert(toString(v1, Type(T. CHAR)) == "'A'");
    assert(toString(v1, Type(T.WCHAR)) == "'A'w");
    assert(toString(v1, Type(T.DCHAR)) == "'A'd");

    auto v2 = Literal(V.INTEGER, 9);
    assert(toString(v2, Type(T. CHAR)) == `'\t'`);
    assert(toString(v2, Type(T.WCHAR)) == `'\t'w`);
    assert(toString(v2, Type(T.DCHAR)) == `'\t'd`);

    auto v3 = Literal(V.INTEGER, 0x80);
    assert(toString(v3, Type(T. CHAR)) == `'\x80'`);
    assert(toString(v3, Type(T.WCHAR)) == `'\u0080'`);
    assert(toString(v3, Type(T.DCHAR)) == `'\U00000080'`);
}


/*
Returns a unary expression string representing the floating point
literal $(D val) of the type $(D ty).

The result will look like: "0x1.2p3L"
 */
private string toString_float(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.FLOAT);
}
body
{
    alias Type.Kind T;
    auto tname = toString(ty);
    string s = toHexString(val.re);

    /* Handle special values.
     */
    switch (s)
    {
        // Assuming ty is a floating point type.
        case       "NaN": return       tname ~ ".nan";
        case  "Infinity": return       tname ~ ".infinity";
        case "-Infinity": return "-" ~ tname ~ ".infinity";
        default: break;
    }

    /* Usual floating point literal. Notice imaginary types.
     */
    bool needcast;

    if (ty.storage != StorageClass.NONE)
    {
        // Floating point literal does not have any storage class.
        needcast = true;
    }
    else
    {
        // Try to reduce the cast by appending a suffix.
        switch (ty.kind)
        {
            case T.FLOAT , T.IFLOAT : s ~= "F"; break;
            case T.DOUBLE, T.IDOUBLE:           break;
            case T.REAL  , T.IREAL  : s ~= "L"; break;

            default:
                needcast = true;
                break;
        }
    }

    /* Deal with imaginary types. Simply append the 'i' suffix.
     */
    switch (ty.kind)
    {
        case T.IFLOAT, T.IDOUBLE, T.IREAL:
            s ~= "i";
            break;

        default: break;
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ tname ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = Literal(V.FLOAT, 0, 0x1.2p34);
    enum t11 = Type(T.FLOAT);
    enum t12 = Type(T.DOUBLE);
    enum t13 = Type(T.REAL);
    enum t14 = Type(T.INT);
    static assert(toString_float(v1, t11) == "0x1.2p34F");
    static assert(toString_float(v1, t12) == "0x1.2p34");
    static assert(toString_float(v1, t13) == "0x1.2p34L");
    static assert(toString_float(v1, t14) == "cast(int) 0x1.2p34");

    enum v2 = Literal(V.FLOAT, 0, real.nan);
    enum t21 = Type(T.FLOAT);
    enum t22 = Type(T.DOUBLE);
    enum t23 = Type(T.REAL);
    enum t24 = Type(T.REAL, STC.CONST);
    static assert(toString_float(v2, t21) == "float.nan");
    static assert(toString_float(v2, t22) == "double.nan");
    static assert(toString_float(v2, t23) == "real.nan");
    static assert(toString_float(v2, t24) == "const(real).nan");

    enum v3 = Literal(V.FLOAT, 0, real.infinity);
    enum t31 = Type(T.FLOAT);
    enum t32 = Type(T.DOUBLE);
    enum t33 = Type(T.REAL);
    enum t34 = Type(T.REAL, STC.CONST);
    static assert(toString_float(v3, t31) == "float.infinity");
    static assert(toString_float(v3, t32) == "double.infinity");
    static assert(toString_float(v3, t33) == "real.infinity");
    static assert(toString_float(v3, t34) == "const(real).infinity");

    enum v4 = Literal(V.FLOAT, 0, -real.infinity);
    enum t41 = Type(T.FLOAT);
    enum t42 = Type(T.DOUBLE);
    enum t43 = Type(T.REAL);
    enum t44 = Type(T.REAL, STC.CONST);
    static assert(toString_float(v4, t41) == "-float.infinity");
    static assert(toString_float(v4, t42) == "-double.infinity");
    static assert(toString_float(v4, t43) == "-real.infinity");
    static assert(toString_float(v4, t44) == "-const(real).infinity");
}


/*
Returns a unary expression string representing the complex literal
$(D val) of the type $(D ty).

The result would look like: "0x1.2p3 + 0x4.5p6i"
 */
private string toString_complex(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.COMPLEX);
}
body
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    /* Handle special case. Note that Complex.infinity does not make
     * sense. We only handle NaN + NaNi.
     */
    if (val.re !<>= 0 && val.im !<>= 0)
    {
        // Assuming ty is a complex type.
        return toString(ty) ~ ".nan";
    }

    /* Split into real and imaginary parts.
     */
    auto re = Literal(V.FLOAT, 0, val.re);
    auto im = Literal(V.FLOAT, 0, val.im);

    // Deduce the types of re and im.
    Type rety, imty;

    bool needcast = (ty.storage != 0);

    // real part
    switch (ty.kind)
    {
        case T.CFLOAT : rety.kind = T.FLOAT ; break;
        case T.CDOUBLE: rety.kind = T.DOUBLE; break;
        case T.CREAL  : rety.kind = T.REAL  ; break;

        default:
            // deduced type should be FLOAT, DOUBLE or REAL
            rety     = deduceType(re);
            needcast = true;
            break;
    }

    // imaginary part should have the same precision as the real part
    switch (rety.kind)
    {
        case T.FLOAT : imty.kind = T.IFLOAT ; break;
        case T.DOUBLE: imty.kind = T.IDOUBLE; break;
        case T.REAL  : imty.kind = T.IREAL  ; break;

        default: assert(0); // does not reach
    }

    /* Separately convert re & im to string using the deduced types.
     */
    auto restr = toString_float(re, rety);
    auto imstr = toString_float(im, imty);

    // Compose a complex literal.
    string s = restr;

    if (startsWith(imstr, "-"))
        s ~= " - " ~ imstr[1 .. $];
    else
        s ~= " + " ~ imstr;

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") (" ~ s ~ ")";
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = Literal(V.COMPLEX, 0, 0x1.2p3, -0x1.45p6);
    enum t11 = Type(T.CFLOAT);
    enum t12 = Type(T.CDOUBLE);
    enum t13 = Type(T.CREAL);
    enum t14 = Type(T.CREAL, STC.CONST);
    static assert(toString_complex(v1, t11) == "0x1.2p3F - 0x1.45p6Fi");
    static assert(toString_complex(v1, t12) == "0x1.2p3 - 0x1.45p6i");
    static assert(toString_complex(v1, t13) == "0x1.2p3L - 0x1.45p6Li");
    static assert(toString_complex(v1, t14) ==
            "cast(const(creal)) (0x1.2p3L - 0x1.45p6Li)");

    enum v2 = Literal(V.COMPLEX, 0, real.nan, real.nan);
    enum t2 = Type(T.CREAL, STC.CONST);
    static assert(toString_complex(v2, t2) == "const(creal).nan");

    enum v3 = Literal(V.COMPLEX, 0, real.infinity, 0);
    enum t3 = Type(T.CDOUBLE);
    static assert(toString_complex(v3, t3) ==
            "double.infinity + 0x0p0i");

    enum v4 = Literal(V.COMPLEX, 0, 0, -real.infinity);
    enum t4 = Type(T.CDOUBLE);
    static assert(toString_complex(v4, t4) ==
            "0x0p0 - idouble.infinity");

}


/*
Returns a unary expression string representing the array literal
$(D val) of the type $(D ty).

The result will look like: "[ 1, 2, 3 ]"
 */
private string toString_array(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.ARRAY);
}
body
{
    alias Type.Kind T;

    /* Build the default-typed array literal [ a, b, c ].
     */
    string s = "";

    // Join all elements by ", "
    if (val.next) // [workaround] CTFE
    foreach (i, e; val.next)
    {
        if (i >= 1)
            s ~= ", ";
        s ~= toString(e);
    }

    // enclosing brackets
    if (s.length)
        s = "[ " ~ s ~ " ]";
    else
        s = "[]";

    /* The array literal is a static array. cast?
     */
    bool needcast;

    auto dedty = deduceType(val);
    assert(dedty.kind == T.SARRAY);

    if (equal(ty, dedty) != false)
    {
        // exact match
    }
    else if (ty.kind == T.ARRAY)
    {
        if (ty.storage == dedty.storage &&
            equal(ty.next[0], dedty.next[0]))
        {
            // The given type is just the dynamic version of the
            // deduced type. Just slicing gives the correct type.
            s ~= "[]";
        }
        else
        {
            needcast = true;
        }
    }
    else
    {
        needcast = true;
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;
    alias makeStruct!(Literal, "kind", "next") Next;

    enum v1 = Literal(V.ARRAY);
    static assert(toString_array(v1, deduceType(v1)) == "[]");

    enum v2 = Next(V.ARRAY,
            [ Literal(V.INTEGER, 1),
              Literal(V.INTEGER, 2) ]);
    enum t2 = Type(T.ARRAY, STC.NONE, [ Type(T.INT) ]);
    static assert(toString_array(v2, t2) == "[ 1, 2 ][]");

    enum v3 = Next(V.ARRAY,
            [ Literal(V.INTEGER, 1),
              Literal(V.INTEGER, 2) ]);
    enum t3 = Type(T.SARRAY, STC.NONE, [ Type(T.SHORT) ], 2);
    static assert(toString_array(v3, t3) == "cast(short[2]) [ 1, 2 ]");
}


/*
Returns a unary expression string representing the associative array
literal $(D val) of the type $(D ty).

The result will look like: "[ 1: "a", 2: "b" ]"
 */
private string toString_assocArray(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.AARRAY);
    assert(val.next.length % 2 == 0);
}
body
{
    /* Keys and values are interleaved: [ key, val, key, val, ... ]
     */
    string s = "";

    for (size_t i = 0; i < val.next.length; )
    {
        if (i > 0)
            s ~= ", ";

        const skey = toString(val.next[i++]);
        const sval = toString(val.next[i++]);
        s ~= skey ~ ": " ~ sval;
    }

    // enclosing brackets
    if (s.length)
        s = "[ " ~ s ~ " ]";
    else
        s = "[]";

    /* Need cast?
     */
    bool needcast;

    if (val.next.length == 0)
    {
        // Empty [] is void[0]; explicit convertion is necessary
        needcast = true;
    }
    else if (ty.storage != StorageClass.NONE)
    {
        needcast = true;
    }
    else
    {
        // Need cast if ty is different from the deduced type
        needcast = !equal(ty, deduceType(val));
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = Literal(V.AARRAY);
    enum t1 = Type(T.AARRAY, STC.NONE, [ Type(T.INT), Type(T.REAL) ]);
    static assert(toString(v1, t1) == "cast(real[int]) []");

    enum v2 = makeStruct!(Literal, "kind", "next")(V.AARRAY,
            [ Literal(V.INTEGER, 1), Literal(V.INTEGER,  10),
              Literal(V.INTEGER, 2), Literal(V.INTEGER, 100) ]);
    enum t2 = Type(T.AARRAY, STC.NONE, [ Type(T.INT), Type(T.INT) ]);
    static assert(toString(v2, t2) == "[ 1: 10, 2: 100 ]");
}


/*
Returns a unary expression string representing the struct literal
$(D val) of the type $(D ty).

The result will look like: "mod.S(42, "abc", var)"
 */
private string toString_struct(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.STRUCT);
}
body
{
    /* Build (a, b, c)
     */
    string s = "";

    // Join all elements by ", "

    if (val.next) // [workaround] CTFE
    foreach (i, e; val.next)
    {
        if (i >= 1)
            s ~= ", ";
        s ~= toString(e);
    }

    // enclosing parens
    if (s.length)
        s = "(" ~ s ~ ")";
    else
        s = "()";

    // Prefix the struct name.
    s = toString(ty.symbol[0]) ~ s;

    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias  Symbol.Kind S;

    enum v1 = makeStruct!(Literal, "kind", "next")(V.STRUCT,
            [ Literal(V.INTEGER, 42),
              Literal(V.STRING, 0, 0, 0, "abc") ]);
    enum t1 = makeStruct!(Type, "kind", "symbol")(T.STRUCT,
            [ Symbol(S.IDENTIFIER, "S") ]);
    static assert(toString_struct(v1, t1) == `S(42, "abc")`);
}


/*
Returns a unary expression string representing the string literal
$(D val) of the type $(D ty).
 */
private string toString_string(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.STRING);
}
body
{
    alias Type.Kind    T;
    alias StorageClass STC;

    // common string types
    enum
    {
        STCimm = STC.IMMUTABLE,

        Tstring  = Type(T.ARRAY, STC.NONE, [ Type(T. CHAR, STCimm) ]),
        Twstring = Type(T.ARRAY, STC.NONE, [ Type(T.WCHAR, STCimm) ]),
        Tdstring = Type(T.ARRAY, STC.NONE, [ Type(T.DCHAR, STCimm) ]),
    }

    /* Build the string literal.
     */
    string s = `"` ~ escapeDString(val.text) ~ `"`;

    // Try to eliminate cast by changing the suffix.
    if (val.suffix != "c" && equal(ty,  Tstring)) val.suffix = "c";
    if (val.suffix != "w" && equal(ty, Twstring)) val.suffix = "w";
    if (val.suffix != "d" && equal(ty, Tdstring)) val.suffix = "d";

    // Since string is UTF-8 by default, the suffix 'c' is unnecessary.
    if (val.suffix != "c")
        s ~= val.suffix;

    // Finish.
    if (!equal(ty, deduceType(val)))
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = makeStruct!(Literal, "kind", "text")(V.STRING, "");
    enum t1 = Type(T.ARRAY, STC.NONE,
            [ Type(T.DCHAR, STC.IMMUTABLE) ]);
    static assert(toString_string(v1, t1) == `""d`);

    enum v2 = makeStruct!(Literal, "kind", "text", "suffix")(V.STRING,
            `abc\ "def" /ghi`, "w");
    enum t2 = deduceType(v2);
    static assert(toString_string(v2, t2) == `"abc\\ \"def\" /ghi"w`);
}


/*
Makes the string $(D str) safely quotable.
 */
private string escapeDString(string str) pure nothrow
{
    string es;

    foreach (i, c; str)
    {
        string r;

        switch (c)
        {
            default: break;

            // these characters must be escaped
            case '\"': r = `\"`; break;
            case '\'': r = `\'`; break;
            case '\\': r = `\\`; break; //`//[workaround] vim syn

            // newlines should be escaped
            case '\r': r = `\r`; break;
            case '\n': r = `\n`; break;

            // EOF should be escaped
            case '\x00': r = `\x00`; break;
            case '\x1A': r = `\x1A`; break;
        }

        // copy on write
        if (es)
        {
            if (r)
                es ~= r;
            else
                es ~= c;
        }
        else
        {
            if (r)
                es = str[0 .. i] ~ r;
        }
    }
    return es ? es : str;
}

unittest
{
    static assert(escapeDString("abcd") == "abcd");
    static assert(escapeDString("\r\n") == `\r\n`);
    static assert(escapeDString(`\"`)   == `\\\"`);
    static assert(escapeDString("\x00") == `\x00`);
    static assert(escapeDString("\x1A") == `\x1A`);
}


/*
Returns the default type of the literal value $(D val).
 */
private Type deduceType(Literal val)
{
    alias    Type.Kind T;
    alias Literal.Kind V;
    alias StorageClass STC;

    enum PVOID = Type(T.POINTER, STC.NONE, [ Type(T.VOID) ]);

    // hub
    switch (val.kind)
    {
        case V.NULL   : return PVOID;
        case V.INTEGER: return deduceIntegerType(val);
        case V.FLOAT  : return deduceFloatType(val);
        case V.COMPLEX: return deduceComplexType(val);
        case V.STRING : return deduceStringType(val);
        case V.ARRAY  : return deduceArrayType(val);
        case V.AARRAY : return deduceAssocArrayType(val);
        case V.STRUCT : return deduceStructType(val);

        default: assert(0); // does not reach
    }
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias makeStruct!(Literal, "kind", "suffix") Suffix;
    alias makeStruct!(Literal, "kind", "next") Next;

    enum v1 = Literal(V.NULL);
    static assert(toString(deduceType(v1)) == "void*");

    enum v2 = Literal(V.INTEGER);
    static assert(toString(deduceType(v2)) == "int");

    enum v3 = Literal(V.FLOAT);
    static assert(toString(deduceType(v3)) == "double");

    enum v4 = Literal(V.COMPLEX);
    static assert(toString(deduceType(v4)) == "cdouble");

    enum v51 = Suffix(V.STRING, "");
    enum v52 = Suffix(V.STRING, "c");
    enum v53 = Suffix(V.STRING, "w");
    enum v54 = Suffix(V.STRING, "d");
    static assert(toString(deduceType(v51)) == "string");
    static assert(toString(deduceType(v52)) == "string");
    static assert(toString(deduceType(v53)) == "wstring");
    static assert(toString(deduceType(v54)) == "dstring");

    enum v61 = Literal(V.ARRAY);
    enum v62 = Next(V.ARRAY, [ Literal(V.FLOAT), Literal(V.INTEGER) ]);
    static assert(toString(deduceType(v61)) == "void[0]");
    static assert(toString(deduceType(v62)) == "double[2]");

    enum v7 = Next(V.AARRAY, [ Literal(V.INTEGER), Literal(V.FLOAT) ]);
    static assert(toString(deduceType(v7)) == "double[int]");
}

// Notice the suffix U and/or L.
private Type deduceIntegerType(Literal val)
{
    alias Type.Kind T;
    T ty = T.INT;

    switch (val.suffix)
    {
        case "U" : ty = T.UINT ; break;
        case  "L": ty = T. LONG; break;
        case "UL": ty = T.ULONG; break;
        default: break;
    }
    return Type(ty);
}

// Notice the suffix F or L with i.
private Type deduceFloatType(Literal val)
{
    alias Type.Kind T;
    T ty = T.DOUBLE;

    switch (val.suffix)
    {
        case "F" : ty = T. FLOAT ; break;
        case "L" : ty = T. REAL  ; break;
        case "i" : ty = T.IDOUBLE; break;
        case "Fi": ty = T.IFLOAT ; break;
        case "Li": ty = T.IREAL  ; break;
        default: break;
    }
    return Type(ty);
}

// Notice the suffix F or L.
private Type deduceComplexType(Literal val)
{
    alias Type.Kind T;
    T ty = T.CDOUBLE;

    switch (val.suffix)
    {
        case "F": ty = T.CFLOAT; break;
        case "L": ty = T.CREAL ; break;
        default: break;
    }
    return Type(ty);
}

// Deduce from the suffix (default is char).
private Type deduceStringType(Literal val)
{
    alias    Type.Kind T;
    alias StorageClass STC;
    T ety = T.CHAR;

    switch (val.suffix)
    {
        case "c": ety = T. CHAR; break;
        case "w": ety = T.WCHAR; break;
        case "d": ety = T.DCHAR; break;
        default : break;
    }
    return Type(T.ARRAY, STC.NONE, [ Type(ety, STC.IMMUTABLE) ]);
}

// Deduce from the first element.
private Type deduceArrayType(Literal val)
{
    alias    Type.Kind T;
    alias StorageClass STC;

    auto ety = Type(T.VOID);
    if (val.next.length)
        ety = deduceType(val.next[0]);
    return Type(T.SARRAY, STC.NONE, [ ety ], val.next.length);
}

// Deduce from the first two elements.
private Type deduceAssocArrayType(Literal val)
in
{
    assert(val.next.length % 2 == 0);
}
body
{
    alias    Type.Kind T;
    alias StorageClass STC;
    auto kty = deduceType(val.next[0]);
    auto vty = deduceType(val.next[1]);
    return Type(T.AARRAY, STC.NONE, [ kty, vty ]);
}

// No way to tell the actual type. Return a dummy type.
private Type deduceStructType(Literal val)
{
    auto ty = Type(Type.Kind.STRUCT);
    ty.symbol = [ Symbol(Symbol.Kind.IDENTIFIER, "struct") ];
    return ty;
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Symbol name
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D Symbol) object represents a symbol, i.e. an identifier or a
template instance. The $(D kind) field indicates which is represented
by the object.

An identifier is (an alias to) a variable, a function, a template, a
template mixin, a package or a module. The identifier has its name, a
possible parent scope and a possible type. The parent scope is another
symbol. The type is available for variables and functions.

A template instance has its name (the name of the instantiated template
itself), a possible parent scope, and template instantiation arguments.
The name and the parent scope are the same as for identifiers.

Example:

In this example $(D std), $(D std.math), $(D sin), $(D var), $(D Temp)
and $(D Mix) are all identifiers; and $(D Inst) is a template instance.
The parent scope of $(D sin) ($(D std.math.sin)) is the module
$(D std.math), and the grandparent scope is the package $(D std).
$(D std) does not have parent scope.
--------------------
import std.math : sin;
int var;
template Temp(int n) {}
mixin Temp!(42) Mix;
alias Temp!(42) Inst;
--------------------
 */
struct Symbol
{
    /**
     * The $(D kind) field indicates the _kind of the symbol. The value
     * can be one of these:
     */
    enum Kind
    {
        /**
         * Identifier. The first element of the $(D type) field is the
         * type (if any) of the symbol.
         */
        IDENTIFIER,

        /**
         * Template instance. The $(D args) field is an array of the
         * template instantiation arguments.
         */
        TEMPLATE,
    }
    Kind kind; /// ditto

    /**
     * The _name of the symbol itself.
     */
    string name;

    /**
     * If the symbol has a _parent scope, the first element of this
     * field, $(D parent[0]), is a $(D Symbol) object of the _parent
     * scope.
     */
    Symbol[] parent;

    /**
     * See the description of the $(D kind).
     */
    TemplateArgument[] args;
    Type[]             type; /// ditto
}


/*
[internal] For convenience.
 */
version (unittest)
private Symbol createSymbol(string[] hier)
{
    Symbol sym;

    foreach (i, id; hier)
    {
        auto si = Symbol(Symbol.Kind.IDENTIFIER, id);

        if (i == 0)
        {
            sym = si;
        }
        else
        {
            si.parent = [ sym ];
            sym = si;
        }
    }
    return sym;
}

unittest
{
    enum sym1 = createSymbol([ "abc" ]);
    static assert(toString(sym1) == "abc");

    enum sym2 = createSymbol([ "abc", "def" ]);
    static assert(toString(sym2) == "abc.def");
}


/**
Ditto
 */
bool equal(in Symbol sa, in Symbol sb)
{
    if (sa.kind != sb.kind)
        return false;

    if (sa.name != sb.name)
        return false;

    /* Compare template instantiation arguments.
     */
    if (sa.kind == Symbol.Kind.TEMPLATE)
    {
        if (sa.args.length != sb.args.length)
            return false;

        foreach (i; 0 .. sa.args.length)
        {
            if (!equal(sa.args[i], sb.args[i]))
                return false;
        }
    }

    /* Compare types. The type is stored in type[0] (for CTFE).
     * type.length == 0 means a symbol is not typed.
     */
    if (sa.type.length || sb.type.length)
    {
        if (sa.type.length != sb.type.length)
            return false; // either one is untyped

        if (!equal(sa.type[0], sb.type[0]))
            return false;
    }

    /* Check ancestors recursively. Doing this last would reduce the
     * depth of the recursion.
     */
    if (sa.parent.length || sb.parent.length)
    {
        if (sa.parent.length != sb.parent.length)
            return false;

        if (!equal(sa.parent[0], sb.parent[0]))
            return false;
    }

    return true;
}

unittest
{
    alias Symbol.Kind S;

    enum s1a = createSymbol([ "x", "y", "a" ]);
    enum s1b = createSymbol([ "z", "y", "a" ]);
    enum s1c = Symbol(S.TEMPLATE, "temp");
    static assert( equal(s1a, s1a));
    static assert( equal(s1b, s1b));
    static assert( equal(s1c, s1c));
    static assert(!equal(s1a, s1b));
    static assert(!equal(s1b, s1c));
    static assert(!equal(s1c, s1a));
}


/**
Ditto
 */
string toString(Symbol sn)
{
    alias   Type.Kind T;
    alias Symbol.Kind S;

    /* The function symbol has a different syntax. Leave it to the
     * toString_function().
     */
    if (sn.type.length && sn.type[0].kind == T.FUNCTION)
    {
        auto ty = sn.type[0];
        sn.type = null; // to prevent infinite recursion
        ty.symbol = [ sn ];

        return toString_function(ty);
    }

    /* Build "Type fully.qualified.name!(args)"
     */
    string s = sn.name;

    // Qualify the name
    if (sn.parent.length)
        s = toString(sn.parent[0]) ~ "." ~ s;

    // Append instantiation arguments.
    if (sn.kind == S.TEMPLATE)
    {
        s ~= "!(";
        if (sn.args) // [workaround] CTFE
        foreach (i, a; sn.args)
        {
            if (i >= 1)
                s ~= ", ";
            s ~= toString(a);
        }
        s ~= ")";
    }

    // Append the type
    if (sn.type.length && sn.type[0].kind != T.NONE)
        s = toString(sn.type[0]) ~ " " ~ s;

    return s;
}

unittest
{
    alias Symbol.Kind S;
    alias   Type.Kind T;
    alias makeStruct!(Symbol, "kind", "name", "type", "parent") ID;

    enum s1 = Symbol(S.IDENTIFIER, "std");
    static assert(toString(s1) == "std");

    enum s2 = Symbol(S.TEMPLATE, "temp", []);
    static assert(toString(s2) == "temp!()");

    enum s3 = ID(S.IDENTIFIER, "math", null, [ s1 ]);
    static assert(toString(s3) == "std.math");

    enum s4 = ID(S.IDENTIFIER, "PI", [ Type(T.REAL) ], [ s3 ]);
    static assert(toString(s4) == "real std.math.PI");

    enum s5 = ID(S.IDENTIFIER, "foo",
            [ makeStruct!(Type, "kind", "next")( T.FUNCTION,
                [ Type(T.VOID) ]) ],
            [ s2 ]);
    static assert(toString(s5) == "void temp!().foo()");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Template argument
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D TemplateArgument) object represents a template instantiation
argument.

A template instantiation argument is a type, a literal value, or a
symbol. The $(D kind) field indicates which kind of template argument
is stored in a $(D TemplateArgument) object. The $(D type) field is for
a type argument. The $(D type) and $(D value) fields are for a value
argument. The $(D symbol) field is for a symbol argument.

Example:

Examining the result of $(D ext.demangle.decodeName).
--------------------
template Temp(T...) {}
alias Temp!(42u) Inst;

Symbol sym = ext.demangle.decodeName(Inst.mangleof);

// The first argument is a value 42 of type uint.
TemplateArgument targ = sym.args[0];
assert(targ.kind == TemplateArgument.Kind.VALUE);
assert(targ.value.integer == 42);
assert(toString(targ.type) == "uint");
--------------------
 */
struct TemplateArgument
{
    /**
     * The $(D kind) field indicates which _kind of argument is stored
     * in this object. The value can be one of these:
     */
    enum Kind
    {
        /**
         * Template type argument. The $(D type) field is the type.
         */
        TYPE,

        /**
         * Template value argument (constant value). The $(D value)
         * field is the value and the $(D type) field is the type of
         * the value.
         */
        VALUE,

        /**
         * Template symbol argument (function, template etc.). The
         * $(D symbol) field is the symbol.
         */
        SYMBOL,
    }
    Kind kind; /// ditto

    /**
     * See the description of the $(D kind).
     */
    Type     type;
    Literal value; /// ditto
    Symbol symbol; /// ditto
}


/**
Ditto
 */
bool equal(in TemplateArgument ta, in TemplateArgument tb)
{
    alias TemplateArgument.Kind A;

    if (ta.kind != tb.kind)
        return false;

    switch (ta.kind)
    {
        case A.TYPE  : return equal(ta.type, tb.type);
        case A.VALUE : return equal(ta.type, tb.type) &&
                              equal(ta.value, tb.value);
        case A.SYMBOL: return equal(ta.symbol, tb.symbol);

        default: assert(0);
    }
}

unittest
{
    alias TemplateArgument.Kind A;
    alias             Type.Kind T;
    alias          Literal.Kind V;
    alias           Symbol.Kind S;

    enum a1a = TemplateArgument(A.TYPE, Type(T.INT));
    enum a1b = TemplateArgument(A.TYPE, Type(T.REAL));
    static assert( equal(a1a, a1a));
    static assert( equal(a1b, a1b));
    static assert(!equal(a1a, a1b));

    enum a2a = TemplateArgument(
            A.VALUE, Type(T.INT), Literal(V.INTEGER, 1));
    enum a2b = TemplateArgument(
            A.VALUE, Type(T.INT), Literal(V.INTEGER, 2));
    static assert( equal(a2a, a2a));
    static assert( equal(a2b, a2b));
    static assert(!equal(a2a, a2b));

    static assert(!equal(a1a, a2a));
}


/**
Ditto
 */
string toString(TemplateArgument ta)
{
    alias TemplateArgument.Kind A;

    switch (ta.kind)
    {
        case A.TYPE  : return toString(ta.type);
        case A.VALUE : return toString(ta.value, ta.type);
        case A.SYMBOL: return toString(ta.symbol);
        default: assert(0);
    }
}

unittest
{
}


